LeetCode Visualizer
How it worksAll visualizations

Step by step · Python

Insertion sort, visualized step by step

Insertion sort works the way most people sort a hand of cards: take the next card and slide it left until it sits in order. It is quadratic in the worst case, but very fast on input that is already nearly sorted.

How it works
Python
arr = [8, 3, 5, 1, 9, 2]

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

print(arr)

How insertion sort works

The array is split into a sorted prefix and an unsorted rest. For each index i, the value arr[i] is saved as key. A second index j walks left through the prefix, shifting every value larger than key one place to the right, and key is written into the gap that opens up.

The example sorts [8, 3, 5, 1, 9, 2]. Watch the 1: it has to travel past every value before it, which is exactly the work a reverse-sorted input would force on every element.

What to watch for when it runs

  1. The sorted prefix grows by one cell on each pass of the outer loop.
  2. Shifts are writes, not swaps — values copy one place right, and key is written only once, at the end.
  3. The execution count on the while line shows how far each key had to travel.

Time and space complexity

Time
O(n²) worst case, O(n) when already sorted
Space
O(1)

Each element moves once for every larger value before it, so the running time is O(n + inversions) — which is why it is the sort of choice for small or nearly-sorted inputs.

Related visualizations

Stuck on your own version?

Paste it into the visualizer and watch your own code run, line by line — bugs included.