How Insertion Sort Works: Step-by-Step Explanation

In this article, we’ll understand how insertion sort algorithm works, using clear examples and visualizations. If you’ve ever sorted playing cards in your hand, you already have an intuitive understanding of how insertion sort works. This algorithm is often one of the first sorting methods that programmers learn, and it’s particularly effective for small data sets or nearly sorted arrays. Let’s break down and understand this algorithm step by step.

Brief Introduction

Insertion sort gets its name from the way it “inserts” each element into its proper position within the sorted portion of the array. The algorithm works by following these steps:

  1. It maintains two portions within the array: a sorted portion (initially containing just the first element) and an unsorted portion (containing the remaining elements).
  2. It picks elements one by one from the unsorted portion, comparing each element with those in the sorted portion.
  3. It shifts larger elements within the sorted portion to the right, creating space to insert the picked element into its correct position.
  4. The process repeats until all elements from the unsorted portion have been moved into their correct positions within the sorted portion, resulting in a fully sorted array.

Refer to this article for more introductory details: Introduction to Insertion Sort Algorithm.

Step-by-Step Walkthrough of Insertion Sort Algorithm

Let’s walk through how to sort the array [7, 3, 5, 1, 8] using the insertion sort algorithm. We’ll break down each step of the algorithm in detail so you can see exactly how this sorting method works.Here’s our starting array:

Step 1: The Initial Sorted Portion

At the start of insertion sort, we assume that the very first element of the array is already sorted. (A single element subarray can always be considered as sorted).

  • The sorted portion consists of just: [7]
  • The remaining unsorted portion: [3, 5, 1, 8]

Visually, we can represent this as below:

In the visualization above, you can see the sorted portion colored in green. Here’s what happens in each step of the insertion sort algorithm:

  1. We look at the next element from the unsorted portion
  2. We compare it with each element in the sorted (green) portion from right to left
  3. If we find any elements that are larger than our current element, we move them one step to the right to make space
  4. Once we find the right spot in the sorted portion (where all elements to the left are smaller than the current element and all elements to the right are greater than the current element), we place our current element there.

Step 2: Inserting the Second Element (3)

Now, let’s take the first element in the unsorted portion, which is 3, and insert it into our sorted portion:

  1. Pick the element 3 from the unsorted portion.
  2. Compare 3 with the last element in the sorted portion, which is 7.
  3. Since 3 is smaller than 7, we shift 7 one position to the right to make space for 3.
  4. Insert 3 into the now vacant position at the beginning of the array.

Here’s the animation of these steps:

  • Before insertion: [7]|[3, 5, 1, 8]
  • After insertion: [3, 7]|[5, 1, 8]

Step 3: Inserting the Third Element (5)

Next element in the unsorted portion is 5:

  1. Take 5 from the unsorted part.
  2. Compare 5 with 7 (the last element in the sorted part).
  3. Since 5 is less than 7, shift 7 to the right.
  4. Now, compare 5 with 3.
  5. Since 5 is greater than 3, its correct position is between 3 and 7.

Here’s the animation of these steps:

  • Before: [3, 7]|[5, 1, 8]
  • After: [3, 5, 7]|[1, 8]

Step 4: Inserting the Fourth Element (1)

Now, let’s insert the element 1, which is the smallest we’ve encountered so far:

  1. Extract 1 from the unsorted portion.
  2. Compare 1 with 7—since 1 is smaller, shift 7 to the right.
  3. Compare 1 with 5—since 1 is smaller, shift 5 to the right.
  4. Compare 1 with 3—since 1 is smaller, shift 3 to the right.
  5. With no more elements to compare in the sorted portion, place 1 at the beginning.

Here’s the animation of these steps:

  • Before: [3, 5, 7]|[1, 8]
  • After: [1, 3, 5, 7]|[8]

Step 5: Inserting the Last Element (8)

Finally, let’s insert the last element, 8:

  1. Take 8 from the unsorted portion.
  2. Compare 8 with 7 (the last element in the sorted part).
  3. Since 8 is greater than 7, it is already in the correct position.
  4. No shifting is needed in this case.

Here’s the animation of these steps:

  • Before: [1, 3, 5, 7]|[8]
  • After: [1, 3, 5, 7, 8]

In summary, insertion sort gradually builds up a sorted portion of the array by inserting elements from the unsorted portion into their correct positions. This continues until the entire array is correctly sorted.

Key Concepts and Operations

Let’s solidify our understanding of insertion sort by explicitly defining the core concepts and operations involved. Think of these concepts as the fundamental building blocks that make insertion sort work.

Maintaining Two Portions

  • The array is divided into two logical portions:
    • Sorted portion (left side) - Elements that are already in correct order
    • Unsorted portion (right side) - Elements yet to be sorted
  • Initially, sorted portion contains just the first element
  • The boundary between sorted and unsorted portions moves right as sorting progresses
  • With each iteration, sorted portion grows and unsorted portion shrinks

Key Selection

  • Select an element from the unsorted portion
  • Let’s call the selected element as “key”
  • This key element needs to be inserted into its correct position in the sorted portion

Comparison

  • Compare the key with elements in the sorted portion
  • Start from the rightmost element of the sorted portion
  • Continue until you find the correct position

Shifting

  • Shift elements larger than the key one position to the right
  • This creates space for inserting the key
  • Only shift elements that are greater than the key

Insertion

  • Place the key in its correct position
  • This position is where all elements to the left are smaller
  • And all elements to the right are larger

What’s Next?

Now that you understand how insertion sort works, you might want to: