Editor

Insertion sort in Python

Insertion sort keeps a sorted part at the front of the list and takes the next value, sliding it left past every bigger value until it fits, like sorting playing cards in your hand.

The arrow keys step through it. Edit the code to try your own input.

How it works

  1. The part left of i is always sorted. At the start that is just the first value.
  2. Take key = nums[i], the next value to place.
  3. While the value just left of j is bigger than key, copy it one place right and move j left.
  4. When the left neighbour is not bigger, or j reaches 0, put key into nums[j].

What to watch

  • Watch the bars left of j shift right one by one, opening a gap that key fills.
  • For a moment two bars have the same height: the bigger value has been copied right, and key waits in its own variable until the gap is ready.
  • Watch 9: it is already bigger than everything before it, so the while loop stops at once. On a sorted list that happens every time, which is the O(n) best case.

The code

def insertion_sort(nums):
    for i in range(1, len(nums)):
        key = nums[i]                # the value to insert
        j = i
        while j > 0 and nums[j - 1] > key:
            nums[j] = nums[j - 1]    # shift the bigger value right
            j -= 1
        nums[j] = key                # drop it into the gap
    return nums

data = [6, 2, 9, 4, 1, 7]
print(insertion_sort(data))
Output
[1, 2, 4, 6, 7, 9]

Open it in the editor · Python Program for Insertion Sort, explained