AlgoVerse

Insertion sort

Like sorting playing cards in your hand: take each item and put it in its place in the sorted part on the left.

Insertion sort works like sorting playing cards in your hand. The left part of the array is always sorted. In each round, the next item (key) is taken out, the larger items in the sorted part move one place to the right, and key goes into the gap.

Read the full explanation ↓
Input:
n=6PDF export

Six mixed numbers that get sorted over a few rounds; good for following by hand.

  1. def insertion_sort(a):
  2. for j in range(1, len(a)):
  3. key = a[j]
  4. i = j - 1
  5. while i >= 0:
  6. if a[i] <= key:
  7. break
  8. a[i + 1] = a[i]
  9. i = i - 1
  10. a[i + 1] = key
  11. return a

Invariant: At the start of each round of the outer loop, a[0..j−1] holds the items that were there at the start, in sorted order.

Start

502142631435

Local variables

Orange = changed in this step

a list

524613

Call stack

  1. insertion_sort()line 1
Step 1 of 70
Black = pick · Orange = key stepcompare: 0/12 · pick: 0/5 · shift: 0/9 · insert: 0/5

    How the work grows with input size

    Average of 12 random graphs per n (fixed seeds). Hollow marker = the input on screen.

    • comparisons
    • shift
    • insert
    • current input (n=6)
    02040608046810121416n = number of itemscomparisonsshiftinsert
    Show as a table
    ncomparisonsshiftinsert
    45.13.33
    610.97.65
    817.6127
    1028.421.39
    1238.729.411
    1454.34313
    1670.858.415
    Explanation

    The idea

    Insertion sort works like sorting playing cards in your hand. The left part of the array is always sorted. In each round, the next item (key) is taken out, the larger items in the sorted part move one place to the right, and key goes into the gap.

    The steps

    1. Start at j = 1; a[0..0] on its own is sorted.
    2. Take out key = a[j].
    3. Walk back with i from j − 1. While a[i] > key, move a[i] one place to the right.
    4. When you reach an item ≤ key (or the start of the array), put key into a[i + 1].
    5. Increase j and repeat.

    Cost

    • Best case (already sorted): each key needs a single comparison, so O(n).
    • Worst case (sorted backwards): key number j has to pass j items, so n(n − 1)/2 moves in total and O(n²).
    • The extra memory is only O(1): the sort happens in place.

    Stability

    Because the loop stops at a[i] ≤ key, equal items never pass each other. Their relative order is kept, so the sort is stable. Watch it on the "repeated items" input.

    What to watch in the trace

    • The i and j arrows under the bars show the two indices, and key is written above the array.
    • An orange bar is the position written in this step. A bar with an orange outline is the one being compared with key.
    • Compare the number of shift steps in the best case and in the worst case.