Introduction to Insertion Sort Algorithm

Insertion Sort Algorithm
🔗
Demo of Insertion Sort With Playing Cards
🔗
Insertion Sort Algorithmic Dance
🔗
Click here to suggest a better video or view suggestions..

Have you ever sorted a hand of playing cards? If so, you’ve probably used a method very similar to insertion sort without even realizing it! Insertion sort is one of the simplest and most intuitive sorting algorithms, making it an excellent starting point for learning about sorting algorithms in computer science. Before we understand how insertion sort works, let’s first understand what sorting means and why it is useful.

What is Sorting?

Sorting is the process of arranging data in a particular sequence or order, typically in ascending or descending order. It’s a fundamental operation in computer science that we encounter daily, often without even realizing it!

For example, think about your everyday interactions with organized information. Whether you’re scrolling through your phone or shopping online, sorting plays a crucial role in making information accessible and meaningful. Here are some common examples you probably use regularly where sorting is applied:

  • Names in a contact list (alphabetical order)
  • Prices of products (lowest to highest)
  • Dates in a calendar (chronological order)
  • Test scores (highest to lowest)

When we sort data, we’re essentially organizing it in a way that makes it easier to search, analyze, and visualize. Whether you’re looking for a specific phone number in your contacts or finding the highest score in a game, sorting makes these tasks much more efficient.

What is Insertion Sort?

Insertion sort is an algorithm used to sort a list of items in ascending, descending or any other custom order. It gets its name from the way it “inserts” each element into its proper position within the sorted portion of the array. Insertion sort builds the final sorted array one element at a time, by continuously picking up new elements and placing them in their correct position among the already sorted elements.

Imagine you’re playing cards, and you want to arrange them in ascending order. Here’s how you naturally do it:

  1. You start with one card in your hand
  2. You pick up the next card and decide whether it should go before or after the first card
  3. As you pick up each new card, you compare it with the cards you’re already holding
  4. You slide cards over to make space when needed
  5. You place the new card in its correct position
  6. You repeat this process until you’ve picked up and positioned all cards

This natural process perfectly illustrates how insertion sort works. The algorithm maintains two portions in the array:

  • A sorted portion (like the cards already arranged in your hand)
  • An unsorted portion (like the cards still facing down on the table)

With each step, it takes one element from the unsorted portion and places it in its correct position within the sorted portion, just like picking up a new card and placing it in the right spot in your hand.

How Does Insertion Sort Work?

Let’s understand the basic steps of insertion sort using a simple example. Imagine we want to sort this list of numbers in ascending order: [5, 2, 8, 1, 9]. Below is how we do it using insertion sort:

  1. First, we take the first element (5). Since it’s alone, it’s already sorted by default:

    • Current state: [5]|[2, 8, 1, 9]
    • (The | symbol shows the division between sorted and unsorted portions)
    • Think of this as having one card in your hand!

  2. Next, we pick up 2 and need to place it in the correct position:

    • We look at the sorted portion [5] and compare 2 with 5
    • Since 2 is smaller than 5, we move 5 one step right
    • We place 2 in the empty spot we created
    • Current state: [2, 5]|[8, 1, 9]
    • Just like sliding a card to make space for a smaller one!

  3. Now, we pick up 8 and find where it belongs:

    • We compare 8 with the last element in our sorted portion (5)
    • Since 8 is larger than 5, we don’t need to move anything
    • We simply place 8 at the end of our sorted portion
    • Current state: [2, 5, 8]|[1, 9]
    • Like adding a higher card to the end of your hand!

  4. Time to position 1:

    • We start comparing from right to left: 8, then 5, then 2
    • Since 1 is smaller than all of them, we need to shift them all right
    • After making space, we place 1 at the beginning
    • Current state: [1, 2, 5, 8]|[9]
    • Similar to sliding all cards right to make room for the smallest card!

  5. Finally, we handle our last number, 9:

    • We compare 9 with 8 (the last element in our sorted portion)
    • Since 9 is larger than 8, it’s already in the right spot
    • Current state: [1, 2, 5, 8, 9]
    • Just like adding the highest card to the end!

And there we have it! Our array is now perfectly sorted in ascending order. Each step involved taking one element and finding its right place among the already sorted elements, just like organizing cards in your hand! For a deeper understanding, you can check out the articles on step-by-step explanation of merge sort algorithm and visualization of merge sort algorithm.

Key Characteristics

  • In-Place Algorithm: Insertion sort performs all operations directly within the original array, requiring only O(1) extra space. It achieves this by shifting elements and inserting each item into its correct position without needing auxiliary storage structures.

  • Stable Sort: When insertion sort encounters equal elements, it preserves their original relative order in the final sorted array. This happens because the algorithm only shifts elements when they are strictly greater than the key being inserted, ensuring that equal elements maintain their initial sequence. This is helpful especially when sorting is performed on a list of objects.

  • Online: Unlike many other sorting algorithms, insertion sort can process data on-the-fly. It maintains a sorted portion of the array and can immediately place new elements in their correct position as they arrive, making it suitable for streaming data applications.

  • Adaptive: Insertion sort’s efficiency improves with partially sorted data. When elements are nearly in order, it requires fewer comparisons and shifts, potentially achieving O(n) time complexity in the best case. The algorithm naturally takes advantage of existing order in the input.

  • Simple Implementation: The algorithm mirrors how we naturally sort items, like organizing cards in hand. Its straightforward approach of comparing and shifting elements makes it easy to understand and implement, particularly suitable for small datasets and learning purposes.

What’s Next?

Now that you understand the basics of insertion sort, you might want to: