Insertion Sort

Grow a sorted prefix one element at a time: take the next value and slide it left past everything larger. Quadratic in general, but linear on nearly-sorted data — which is why real sorts fall back to it on small runs.

time O(n²) worst, O(n) nearly sorted

space O(1)

Input

Press Tab out of the box or click Resetto regenerate frames from the current input.

Visualization

No frames yet — edit input and click Run.

—

Pseudocode

for i in 1..n-1:
  key = a[i]
  j = i - 1
  while j >= 0 and a[j] > key:
    a[j+1] = a[j]; j -= 1
  a[j+1] = key