SortingSorting

Insertion Sort

Build a sorted prefix by inserting each new element into its correct place among the ones before it.

Learn Insertion Sort →
29
0
10
1
14
2
37
3
13
4
5
5
42
6
21
7
1/47Start with 8 elements. The prefix a[0..0] of length one is trivially sorted; each round inserts the next element into it.
Key being insertedComparingShifted rightSorted prefix
PseudocodeLearn Insertion Sort →
1for i in 1 .. n-1:
2  key = a[i]
3  j = i - 1
4  while j >= 0 and a[j] > key:
5    a[j+1] = a[j]
6    j = j - 1
7  a[j+1] = key
Complexity
best O(n)
avg O(n²)
worst O(n²)
space O(1)
Speed