Insertion sort is a simple
sorting algorithm that builds the final
sorted array (or list) one item at a time. It is much less efficient on large lists than more advanced algorithms such as
quicksort,
heapsort, or
merge sort. However, insertion sort provides several advantages:
- Simple implementation: Bentley shows a three-line C version, and a five-line optimized version
- Efficient for (quite) small data sets, much like other quadratic sorting algorithms
- More efficient in practice than most other simple quadratic (i.e., O(n2)) algorithms such as selection sort or bubble sort
- Adaptive, i.e., efficient for data sets that are already substantially sorted: the time complexity is when each element in the input is no more than places away from its sorted position
- Stable; i.e., does not change the relative order of elements with equal keys
- In-place; i.e., only requires a constant amount O(1) of additional memory space
- Online; i.e., can sort a list as it receives it