Insertion sort
Insertion sort is another elementary sorting algorithm whose idea is rather easy to understand. The algorithmic idea of insertion sort can be stated as follows:
Assume that the sub-array with the first \(i\) elements of the array is already sorted. In the first round, \(i = 1\).
Take the \(i+1\):th element \(e\). Shift the last elements in the sorted sub-array prefix one step right until the correct position for \(e\) is reached. Insert \(e\) to that position.
Now the sub-array of the first \(i+1\) elements is sorted.
Repeat until the whole array is sorted.
In pseudo-code, insertion sort can be described as follows. Please notice that, unlike in Introduction to Algorithms (Aalto access), we start array indexing from \(0\), not from \(1\).
An implementation for integer arrays in Scala, as well as a generic version in C++, look quite similar:
def insertionSort(a: Array[Int]): Unit =
var i = 1
while i < a.length do
val element = a(i)
var j = i;
while j > 0 && element < a(j - 1) do
a(j) = a(j - 1)
j -= 1
a(j) = element
i += 1
template <typename T>
void insertionsort(std::vector<T> &array) {
const std::size_t n = array.length;
for(std::size_t i = 1; i < n; i++) {
T element = array[i];
std::size_t j = i;
while (j > 0 and element < array[j - 1]) {
array[j] = array[j - 1];
j--;
}
array[j] = element;
}
}
Example: Insertion sort
Some properties of the algorithm:
Only few indices and the element currently moved are stored outside the array at any point of time. Thus the amount of extra memory required is \(\Theta(1)\) and the algorithm works in place.
It is stable because we always find the rightmost position where the currently considered element belongs to, meaning that it is never moved left past an equal element.
Running time analysis
In the following analyses it is assumed that both (i) the comparison of two elements, as well as (ii) the array accesses are constant-time operations.
In the best case, insertion sort runs in time \(\Theta(n)\). To see this, consider how the algorithm behaves on arrays that are already sorted. In such arrays, in each round, the next element considered is already at its correct position and this can be detected by using just one comparison and no shifts.
Example: Insertion sort best case
In the worst case, the running time of the algorithm is \(\Theta(n^2)\). To see this, consider an array of \(n\) distinct elements that is sorted in reverse order. Now
the second element is moved 1 steps,
the third element is moved 2 steps,
and so on, and
the \(n\):th element is moved \(n-1\) steps.
Each move of \(i\) steps induces the same amount of shifts. Therefore, at the \(i\):th round the algorithm performs \(\Theta(i)\) comparisons and array accesses. Thus the running time recurrence is \(T(n) = \Theta(n) + T(n-1) = \Theta(n^2)\).
Example: Insertion sort worst case
What about average case performance? Consider an array consisting of \(n\) distinct random elements. At each iteration, when moving the \(i\):th element \(a_i\) to its correct position, there are on average \(i/2\) elements in the sub-array \(\Arr{a_0 .. a_{i-1}}\) that are smaller than \(a_i\). Therefore, the work on average is \(\sum_{i=1}^{n-1} i/2 = \Theta(n^2)\).
How about the performance on a specific application? This depends on the inputs that the application provides. If the input is usually almost sorted already, insertion sort may work fine in practice. But if the inputs are usually in random order or in some order causing many elements to be moved long distances, we should probably consider some other algorithm.
Observe that insertion sort code is very “compact” (small constants) and the memory accesses are very local. Therefore, for small arrays, insertion sort can be quite competitive as we will see later.
If the element comparisons are expensive, one could use binary search for finding the correct place for each insertion. This causes number of comparisons to drop to \(\Oh{n \Lg n}\) in the worst case. But the overall running time stays \(\Theta(n^2)\) as the shifts still need to be performed.
Experimental evaluation
The plot below compares the performance of the above Scala implementation of
insertion sort to Selection sort and
the sorted method for Scala arrays.
As we can see,
insertion sort is somewhat faster than selection sort
on these input arrays consisting of random integers.
However, their performance scales similarly and
they are not that efficient as the algorithm in the sorted method
on these inputs.