Insertion Sort
Implementation:
for i ← 1 to length(A) j ← i while j > 0 and A[j-1] > A[j] swap A[j] and A[j-1] j ← j - 1
The idea is dead simple: for every element in the array (i-loop), find the location where it belongs in the array and move it there (j-loop).
In the j-loop, j always points to the next unsorted element; if j is bigger than j-1 the two are swapped, j is decreased, and the process is repeated until the element reaches its place.
In python:
def insertion_sort(s): for i in range(1,len(s)): j = i while j > 0 and s[j] < s[j-1]: s[j], s[j-1] = s[j-1], s[j] j -= 1 return s
Analysis
The outer loop runs exactly n-1 times.
The inner loop runs:
- In the best case, never: the array is already sorted
- In the worst case, j-1 times for every iteration of the outer loop (the array is reversed). This is the arithmetic series:
T(N) = \sum_{j = 2}^{n} (j – 1) = \frac{n(n-1)}{2} = O(N^2)
\]