Insertion sort visualization

Insertion sort is a sorting algorithm that works the way many people sort playing cards: it keeps a sorted hand, takes the next element, and slides it left until it sits in the right place. The sorted part grows by one element on every pass.

How it works

1. Treat the first element as a sorted part of length one.
2. Take the next element, the key.
3. Compare the key with the sorted value on its left. While that value is greater, shift it one place to the right.
4. When a smaller or equal value is found, or the front is reached, drop the key into the gap.
5. Repeat until every element has been inserted.

A worked example of insertion sort

Sort [5, 2, 4, 6, 1, 3]. The first value, 5, starts as the sorted part. Each pass takes the next value as the key and slides it left:

1. Key 2: shift 5 one place right, drop it at index 0 (1 comparison). [2, 5, 4, 6, 1, 3]
2. Key 4: shift 5 one place right, drop it at index 1 (2 comparisons). [2, 4, 5, 6, 1, 3]
3. Key 6: nothing to shift, drop it at index 3 (1 comparison). [2, 4, 5, 6, 1, 3]
4. Key 1: shift 6, 5, 4, 2 one place right, drop it at index 0 (4 comparisons). [1, 2, 4, 5, 6, 3]
5. Key 3: shift 6, 5, 4 one place right, drop it at index 2 (4 comparisons). [1, 2, 3, 4, 5, 6]

In total: 12 comparisons and 14 writes (9 shifts plus 5 placements of a key). Key 6 stayed where it was after one comparison, which is why sorted input is cheap, and key 1 passed the whole sorted part, which is why reversed input is expensive.

Insertion sort pseudocode

Indexes start at 0, as in the code of this lesson. A is the array and n is its length.

INSERTION-SORT(A, n)
1  for i = 1 to n - 1
2      key = A[i]
3      j = i - 1
4      while j >= 0 and A[j] > key
5          A[j + 1] = A[j]
6          j = j - 1
7      A[j + 1] = key

Line 4 tests j >= 0 first, so the loop never reads before the start of the array. Line 7 always writes the key, even when it did not move.

Time and space complexity

In the worst case, a reversed array, each key slides all the way to the front: about n²/2 comparisons and shifts. The work is proportional to the number of inversions, pairs that are out of order.

Complexity

Best case time	O(n)
Average case time	O(n²)
Worst case time	O(n²)
Extra space	O(1)

• Best, O(n): the array is sorted, so each key needs one comparison and no shift.
• Average, O(n²): on shuffled input a key passes about half of the sorted part.
• Worst, O(n²): a reversed array, where every key passes the whole sorted part.
• Space, O(1): it sorts in place.

It is also stable, because a key stops in front of an equal value instead of passing it.

When to use it, and when not to

• Use it for small arrays, where its low overhead beats fancier algorithms.
• Use it for nearly sorted data, which it sorts very quickly.
• It is a common finishing step in faster algorithms, which often switch to insertion sort for small pieces.
• Avoid it for large, shuffled data. Use an O(n log n) algorithm there.

Where insertion sort is used

• Inside library sorts. C++'s std::sort in libstdc++ finishes ranges of 16 or fewer elements with insertion sort. Python's list.sort uses a binary variant of it to build short sorted runs before merging them. Java's Arrays.sort for primitive arrays also switches to insertion sort on small ranges. For tiny inputs its low overhead beats the recursion of faster algorithms.
• Data that arrives one value at a time. After every pass the part seen so far is sorted, so the algorithm can keep a list in order as values come in. Each new value costs one insertion.
• Nearly sorted data. The work is about n plus the number of inversions, so a list in which only a few items are out of place, such as a table re-sorted after one row changed, takes close to O(n) time.

Common mistake and edge cases

Related algorithms and variations

Binary insertion sort finds the place for the key with binary search. That cuts the comparisons to about log n per key, but the shifts remain, so the total is still O(n²). Shellsort, published by Donald Shell in 1959, runs insertion sort on elements that are a gap apart and shrinks the gap to 1, so values travel long distances early.

Compare it with bubble sort (bubble sort vs insertion sort) and selection sort (selection sort vs insertion sort). For large inputs, merge sort takes over (insertion sort vs merge sort), and quick sort often hands its small ranges back to insertion sort.