Insertion sort

O(n²)

Insertion sort grows a sorted region on the left, one element at a time. It takes the next value, slides it leftwards past every larger neighbour, and drops it into the gap. It is simple, stable, and very fast on nearly-sorted data — O(n) best case — which is why real libraries use it for small or almost-sorted inputs.

Array
Edit the input and press Play

How it works

  1. Take the next element to the right of the sorted region as the "key".
  2. Compare it with the elements to its left, shifting each larger one one step right.
  3. Drop the key into the gap that opens up — the sorted region is now one longer.
  4. Repeat until every element has been inserted.

Pseudocode

1insertionSort(a):                   # O(n²)2  for i from 1 to n-1:3    key ← a[i]4    j ← i - 15    while j ≥ 0 and a[j] > key:      # shift bigger ones right6      a[j+1] ← a[j]7      j ← j - 18    a[j+1] ← key                     # drop key into the gap