Insertion sort takes as input an array whose values are in an arbitrary order and it permutes them in-place such that they end up in increasing order.
Input:
7 2 6 4 3 8 1
Output:
1 2 3 4 6 7 8
Insertion sort is one of the simpler sorting algorithms. Despite this, it is practically useful because it works very well on modern computers for small arrays, for which it may outperform algorithms with a better asymptotic complexity such as quick sort or merge sort.
How It Works – Overview
Insertion sort is typically implemented as an iterative algorithm.
At each step, there is a prefix of the array that is known to be sorted, called the green segment.
The other elements in the array are in an arbitrary order.
The idea is to insert into this segment, at the right position, the element positioned just after it.
2 6 7 4 3 8 1
^^^^^
green segment
2 4 6 7 3 8 1
^^^^^^^
segment known to be sorted after inserting 4
To implement this, we remember the current element in a temporary location.
4 = temporary location
2 6 7 4 3 8 1 (initial)
We shift by one position towards the right all elements in the green segment that are larger than the current element.
4 = temporary location
2 6 7 7 3 8 1 (shift 7 towards the right)
2 6 6 7 3 8 1 (shift 6 towards the right)
We place the current element in the position freed by the last element shifted.
4 = temporary location
2 4 6 7 3 8 1
This increases the length of the green segment by one element.
We repeat this insertion process until the entire array is known to be sorted.
Initially, the segment known to be sorted consists of just the first element in the array, which is obviously sorted.
7 2 6 4 3 8 1
^
segment known to be sorted consists of just one element
We keep track of this segment by keeping a pointer to the element just past the end of the segment.
7 2 6 4 3 8 1
^
i
We keep track of the position of the current element by using another pointer, which initially matches i.
j
v
7 2 6 4 3 8 1
^
i
We repeatedly swap the current element with the previous one as long as the previous element is smaller.
j
v
2 7 6 4 3 8 1
^
i
Once j hits the beginning of the array or the previous element is larger, we have finished inserting the current element. We forget about j, increase i and repeat the entire process.
2 7 6 4 3 8 1
^
i
Page 1 – Introduction and Overview
Page 2 – How to Implement Insertion Sort in C
Page 3 – Time Complexity