Insertion Sort

#How does it work?

Insertion sort is like sorting playing cards in your hand: you slide each new card into the right place among the cards that are already in order.

The left part of the array is always sorted among itself. The next element (the key) is taken; the larger elements to its left shift one place right, and the key drops into the gap.

If the array is nearly sorted, very few shifts are needed. That is why insertion sort is very fast in practice on small and nearly sorted arrays.

#Live animation

for i = 1 to n - 1
  key = a[i]; j = i - 1
  while j >= 0 and a[j] > key
    a[j + 1] = a[j]; j = j - 1
  a[j + 1] = key

#Step by step

1. 01Start from the second element; the first one alone is a sorted part.
2. 02Take the next element (the key).
3. 03Shift every element in the sorted left part that is larger than the key one place right.
4. 04When you reach an element that is smaller or equal, or the start of the array, put the key into the gap.
5. 05Continue with the next element; once the last one is placed, the array is sorted.

#Example code

The same algorithm in 8 languages. Every program is compiled, run and checked to print the same output.

def insertion_sort(a: list[int]) -> None:
    for i in range(1, len(a)):
        key = a[i]
        j = i - 1
        # Shift larger elements of the sorted part one place right.
        while j >= 0 and a[j] > key:
            a[j + 1] = a[j]
            j -= 1
        a[j + 1] = key


numbers = [5, 1, 4, 2, 8, 3]
insertion_sort(numbers)
print(*numbers)

#Complexity

On an already sorted array each element stays put after one comparison: n-1 comparisons in total, so O(n). On a reversed array every element shifts all the way to the front, about n²/2 operations. It never moves equal elements past each other, so it is stable.

#When to use it?

One of the best choices for small arrays (up to a few dozen elements) and nearly sorted data. That's why real-world hybrids such as Timsort sort small chunks with insertion sort. It also works well when data arrives piece by piece (online).

#Practice

Log in to answer questions and save your progress.

#Up next

Lessons that build on this one:

• Merge Sort
• Shell Sort