An insertion sort starts from the first element in the list, and then for each element will check with the previous one to see if it is smaller than it. If so, it will repeatedly swap backwards until the element before it is not smaller.
The loop invariants are:
- When looking at the sublist from i+1 onwards, all the entries are greater than the sublist up to i.
- Everything to the left of the i-th element is sorted in ascending order.
To increment the loop, we increase i. If the invariant breaks, we take steps to restore the invariance. Those steps are the actual algorithm.
Complexity
The complexity is \(O(N^{2})\). In practice, it is about \(\frac{1}{4}N^{2}\) compared to \(\frac{1}{2}N^{2}\) of selection sort. The reason is that insertion sort, on average, only has to swap about half the number of entries backward to satisfy the invariant.
The best case scenario is when the list is already sorted. Then the algorithm takes linear time.
The worst case is when the list is sorted in the reverse order. Then the algorithm is effectively the selection sort.
So \(o(N)\) and \(O(N^{2})\).
Properties
- The sorting is in-place. No extra memory is needed, and is thus useful in tight memory situations.
- It is a stable sort.
- For a partially sorted list, the insertion sort performs in linear time. This is because the number of exchanges is the number of inversions.
- It can sort a list as it is received (also known as online).
- It requires more writes than selection sort, and may be at a disadvantage if writing is expensive.
Implementations
Python
def insertion_sort(lst, comparator=None):
"""
Insertion sort. It takes in a list of objects and sorts them based
on the comparator. It only works with a list.
Keyword Arguments:
lst -- List to sort
comparator -- Comparator function. It should take in two arguments, and
return -1 if the left is smaller, 1 if the right is smaller,
and 0 if they are equal. If none is provided, then it will
assume a numerical sort.
"""
if not comparator:
def comp(left, right):
if left < right:
return -1
elif left > right:
return 1
else:
return 0
comparator = comp
for index in xrange(1, len(lst)):
value = lst[index]
previous = lst[index-1]
offset = 0
while comparator(value, previous) < 0:
lst[index - offset] = previous
lst[index - offset - 1] = value
offset += 1
if index - offset < 1:
break
previous = lst[index - offset - 1]
C++
#include <algorithm>
#include <vector>
// Pass in the start and stop iterators to the vector.
void insertion_sort(std::vector<int>::iterator const & begin,
std::vector<int>::iterator const & end);
void insertion_sort(std::vector<int>::iterator const & begin,
std::vector<int>::iterator const & end)
{
for(std::vector<int>::iterator iter = begin + 1;
iter != end; ++iter)
{
int value = *iter;
int previous = *(iter - 1);
unsigned int offset = 0;
while (value < previous)
{
std::iter_swap(iter - offset, iter - offset -1);
++offset;
value = *(iter - offset);
previous = *(iter - offset - 1);
if (iter - offset == begin)
{
break;
}
}
}
}