Skip to content

Insertion Sort: A Simple, Efficient Sorting Algorithm

Updated: at 03:26 AM

Insertion sort is a simple sorting algorithm that builds a final sorted array one element at a time. It iterates through an array, removes one element, finds the location where that element belongs in the sorted list, and inserts it there. Insertion sort has best-case O(n) time complexity when the array is already sorted, but worst and average case O(n^2) complexity.

Table of Contents

Open Table of Contents

How Insertion Sort Works

The insertion sort algorithm consists of the following steps:

  1. Start with an unsorted array (list).

  2. Assume the first element is already sorted. Set a marker for the next element to insert.

  3. Select the next element to be inserted into the sorted array. Compare it with the elements in the sorted array from right to left.

  4. Shift elements in the sorted array that are greater than the element to be inserted to create space for insertion.

  5. Insert the element into its correct position by shifting elements.

  6. Set the marker to the next element to be inserted.

  7. Repeat steps 3-6 until the entire array is sorted.

This can be visualized as sorting a hand of playing cards. We remove one card at a time, then place it in its correct position by shifting other cards to the right.

Pseudocode for Insertion Sort


   marker = 1

   while marker < length(array)

      valueToInsert = array[marker]
      holePosition = marker

      while holePosition > 0 and array[holePosition-1] > valueToInsert
         array[holePosition] = array[holePosition-1]
         holePosition = holePosition - 1

      end while

      array[holePosition] = valueToInsert

      marker = marker + 1

   end while

end insertionSort

The pseudocode above demonstrates the key steps of the algorithm:

  1. Start the marker at the second element, assuming the first element is sorted.

  2. Store the value to insert from the marker position.

  3. Find the hole position by comparing the value to insert with elements to the left. Shift elements greater than the value to the right.

  4. When the correct position is found, insert the value at the hole position.

  5. Increment the marker and repeat for the next unsorted element.

Implementing Insertion Sort in Python

Here is an implementation of insertion sort in Python:

def insertion_sort(arr):
    for i in range(1, len(arr)):
        key = arr[i]
        j = i-1
        while j >= 0 and key < arr[j] :
                arr[j + 1] = arr[j]
                j -= 1
        arr[j + 1] = key

arr = [12, 11, 13, 5, 6]

This implements the exact steps we outlined in the pseudocode earlier:

Explanation of the Code

Let’s break down what the Python code is doing:

This implements the shifting and insertion steps of the algorithm correctly in Python.

Time Complexity

The time complexity of insertion sort depends on the initial ordering of the array:

So insertion sort is very fast if the array is already or nearly sorted. But for reverse sorted or random arrays, it is inefficient compared to algorithms like quicksort and mergesort.

Optimized Insertion Sort in Python

We can optimize the insertion sort implementation by avoiding shifting elements repeatedly for each insertion. This is done by using swaps instead of shifting.

Here is an optimized version:

def insertion_sort(arr):
    for i in range(1, len(arr)):
        key = arr[i]
        j = i - 1
        while j >= 0 and key < arr[j]:
            arr[j], arr[j + 1] = arr[j + 1], arr[j]
            j -= 1

The only change is swapping arr[j] and arr[j+1] instead of shifting arr[j] to the right repeatedly.

This reduces the number of assignments per insertion from O(n) to O(1) by using swapping. But the time complexity remains the same asymptotically.

Insertion Sort Applications

Insertion sort has some advantages that lend itself to certain applications:

Some examples where insertion sort is preferred:

So while less efficient overall than O(n log n) sorts, insertion sort still has many uses cases due to its simplicity, small data efficiency, stability, and in-place nature.

Step-By-Step Examples

Let’s go through a few hand worked examples of insertion sort on different array inputs to demonstrate how the algorithm works.

Example 1: Sort [6, 5, 3, 1, 8, 7, 2, 4]

Pass 1:

Start with 6 assumed sorted. Insert 5 before 6. [5, 6, 3, 1, 8, 7, 2, 4]

Pass 2:

Insert 3 before 5. [3, 5, 6, 1, 8, 7, 2, 4]

Pass 3:

Insert 1 before 3. [1, 3, 5, 6, 8, 7, 2, 4]

Pass 4:

8 is greater than preceding numbers. Insert 8 after 6. [1, 3, 5, 6, 8, 7, 2, 4]

Pass 5:

Insert 7 before 8. [1, 3, 5, 6, 7, 8, 2, 4]

Pass 6:

Insert 2 before 7. [1, 3, 5, 6, 2, 7, 8, 4]

Pass 7:

Insert 4 before 7. [1, 3, 5, 6, 2, 4, 7, 8]

The final sorted array is [1, 2, 3, 4, 5, 6, 7, 8].

Example 2: Sort [2, 1, 4, 5, 3]

Pass 1:

2 is assumed sorted. Insert 1 before 2.
[1, 2, 4, 5, 3]

Pass 2:

4 is greater than preceding. Insert after 2. [1, 2, 4, 5, 3]

Pass 3:

5 is greater than preceding. Insert after 4. [1, 2, 4, 5, 3]

Pass 4:

Insert 3 before 5. [1, 2, 4, 3, 5]

The sorted array is [1, 2, 3, 4, 5].

Example 3: Sort [1, 5, 2, 4, 3]

Pass 1:

1 is assumed sorted. 5 is greater, so insert after 1. [1, 5, 2, 4, 3]

Pass 2:

Insert 2 before 5. [1, 2, 5, 4, 3]

Pass 3:

Insert 4 after 5. [1, 2, 5, 4, 3]

Pass 4:

Insert 3 before 4. [1, 2, 5, 3, 4]

The final sorted array is [1, 2, 3, 4, 5].

These examples illustrate how insertion sort increments builds the sorted array by inserting elements into the correct positions at each pass.

Insertion Sort Complexity Analysis

Let’s analyze the time and space complexity of insertion sort in detail.

Time Complexity

So insertion sort is efficient for small n or nearly sorted data but inefficient for large unsorted arrays. Its quadratic time complexity makes it impractical for sorting large data sets.

Space Complexity

Insertion sort has the advantage of minimal memory usage as no additional storage is needed beyond the input array itself.


So in summary, insertion sort is simple to implement, efficient for small or mostly sorted data, stable, and has constant O(1) space complexity. But its quadratic O(n^2) time complexity makes it inefficient for large unsorted arrays.

Comparison with Other Sorting Algorithms

How does insertion sort compare to other common sorting algorithms?

Insertion sort occupies a unique niche of being faster than basic quadratic sorts and stable with minimal memory usage. But for larger data sets, O(n log n) sorts will be faster.

Common Mistakes to Avoid

Some common mistakes to avoid when implementing insertion sort:

Carefully following the exact algorithm, using the optimized swap approach, and testing edge cases will help avoid these mistakes.


Insertion sort is a foundational in-place sorting algorithm that builds the final sorted array incrementally by inserting elements into position one by one. It has O(n) best case time but O(n^2) worst and average case performance. The simplicity, stability, and low space complexity of insertion sort make it ideal for small or nearly sorted data sets. But for larger arrays, O(n log n) algorithms will be more performant. Insertion sort continues to find uses in niche applications like online sorting where incremental insertion is needed. A strong grasp of this fundamental algorithm provides the basis for understanding more complex sorting techniques.