Insertion sort is a primitive sorting algorithm that sorts in ascending order. The idea is that we do passes for each element, then another iterations to check if its sorted.
It has a time complexity of and . It’s slow in the worst case! So we use other algorithms.
Implementation
Below is an implementation in C++:
Proof
For correctness, we can use a loop invariant that suggests: at the start of each iteration of the for
loop, the sub-array list[0:i - 2]
consists of the elements originally in that sub-array but in sorted order.1
- Base case: we have
top = 1
. Since we’re dealing with a single element-large sub-array, this is obviously already sorted. - In the loop: intuitively this holds by how it works. We slowly move the values one by one until it finds a proper position for
list[i]
. - Termination: the loop terminates after we exceed
list.size()
. This tells us that the subarraylist[0:n - 1]
contains the same elements but sorted in the loop.
Footnotes
-
From CLRS’ Introduction to Algorithms. ↩