Insertion Sort Visualization — Step by Step

The card player’s algorithm

Insertion Sort is how most people sort a hand of playing cards without being taught: keep the cards on the left sorted, pick up the next card, and slide it left until it fits. The array works the same way. The first element alone counts as a sorted prefix of length one. Then, one element at a time, the algorithm picks up the next value (the key), walks backward through the sorted prefix, and drops the key into its correct slot. After the last insertion, the sorted prefix *is* the array.

Step 1: Pick up the key

Take [5, 2, 8, 1]. The prefix [5] is trivially sorted. Pass one picks up the key 2 and remembers it in a variable — this matters, because its slot in the array is about to be overwritten. Now compare backward: is 5 greater than 2? Yes, so 5 shifts right into the key’s old slot, giving [5, 5, 8, 1] for a moment. There is nothing left of 5 to compare, so the key drops into index 0: [2, 5, 8, 1]. The sorted prefix is now [2, 5].

Step 2: Shift, don’t swap

Watch what the inner loop does: it never swaps two elements. It copies each too-large element one slot right, then writes the key once at the end. Inserting a key past k larger elements costs k+1 writes, where a swap-based version like Bubble Sort would cost 3k (each swap is three assignments). Continuing the example: key 8 compares against 5, is not smaller, and stays put immediately — one comparison, zero shifts. Key 1 shifts 8, 5, and 2 right, then lands at index 0: [1, 2, 5, 8]. Done.

Why nearly-sorted input is almost free

Here is the property that keeps Insertion Sort alive in real systems: the inner loop stops the instant it finds an element not greater than the key. If every element is already close to its final position, each key shifts only a step or two, and the whole sort runs in roughly O(n + d) time, where d is the number of inversions (out-of-order pairs). Fully sorted input costs exactly n−1 comparisons — a genuine O(n) best case. It is also an *online* algorithm: it can sort a stream, inserting each new arrival as it comes.

The quadratic cliff

On random input the average key must shift past about half the sorted prefix, so total work sums to roughly n²/4 comparisons and shifts — the average and worst cases are O(n²). Reverse-sorted input is the disaster scenario: every key walks the entire prefix, n(n−1)/2 shifts in total. Past a few dozen elements, an O(n log n) algorithm like Merge Sort or Quick Sort pulls away decisively — race them and the divergence is visible even at 30 bars.

Where it survives in production

Insertion Sort is the quadratic sort that real libraries actually ship. Timsort — the standard sort in Python and for objects in Java — uses a variant of it to build up short runs, and many quicksort implementations hand small partitions (commonly under ~16 elements) to Insertion Sort, because at that scale its tiny constant factor and cache-friendly sequential access beat the bookkeeping overhead of recursion. Small n, low overhead, stable, adaptive: for the base case of a hybrid sort, that is exactly the right shape.

JavaScript

function insertionSort(arr) {
  for (let i = 1; i < arr.length; i++) {
    const key = arr[i];
    let j = i - 1;
    while (j >= 0 && arr[j] > key) {
      arr[j + 1] = arr[j]; // shift right to make room
      j--;
    }
    arr[j + 1] = key;
  }
  return arr;
}

Python

def insertion_sort(arr):
    for i in range(1, len(arr)):
        key = arr[i]
        j = i - 1
        # walk left through the sorted prefix
        while j >= 0 and arr[j] > key:
            arr[j + 1] = arr[j]  # shift right to make room
            j -= 1
        arr[j + 1] = key
    return arr

Java

public static void insertionSort(int[] arr) {
    for (int i = 1; i < arr.length; i++) {
        int key = arr[i];
        int j = i - 1;
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j]; // shift right to make room
            j--;
        }
        arr[j + 1] = key;
    }
}