Insertion Sort
EasyGrow a sorted prefix by lifting each new element out and shifting bigger values right until it drops into place.
comparison sortstableadaptive
TimeO(n^2), O(n) on nearly sorted input
SpaceO(1)
InputComma separated numbers
12
0
11
1
13
2
5
3
6
4
The first element is a sorted prefix of length one.
comparisons0shifts0
1 / 17
for i from 1 to n-1:
key = a[i]; j = i - 1
while j >= 0 and a[j] > key:
a[j+1] = a[j]; j--
a[j+1] = key
Why it matters
The fastest simple sort on small or nearly sorted arrays, which is why real sorts fall back to it.
Keyboard
space play← → stepr restartctrl K search
More in Sorting
Next visualiser
Merge Sort