Insertion Sort
Insertion sort mimics the way a card player sorts a hand of cards. You pick up cards one at a time and insert each new card into its correct position among...
Building a Sorted Sequence Incrementally
Insertion sort mimics the way a card player sorts a hand of cards. You pick up cards one at a time and insert each new card into its correct position among the cards already in your hand. At any point, the cards you are holding are sorted, and you extend the sorted sequence one element at a time.
In algorithm form, insertion sort maintains a sorted prefix of the array and extends it by one element per iteration. For each element starting at index 1, extract the element into a temporary variable, then shift all sorted elements that are greater than this extracted element one position to the right, creating a gap, then place the extracted element in that gap.
Consider the array 5, 2, 4, 6, 1, 3. Start with the sorted prefix containing only 5. Extract 2 and compare it to 5. Since 5 is greater than 2, shift 5 right to get 5, 5, 4, 6, 1, 3 and insert 2 at index 0: 2, 5, 4, 6, 1, 3. Now extract 4. Shift 5 right: 2, 5, 5, 6, 1, 3. Insert 4: 2, 4, 5, 6, 1, 3. Continue until the array is fully sorted: 1, 2, 3, 4, 5, 6.
Time complexity is O(n) in the best case when the array is already sorted because no shifting occurs. Average case is O(n squared) because each element is compared to roughly half the sorted prefix on average. Worst case is O(n squared) when the array is reverse sorted, requiring maximum shifting at each step. Space complexity is O(1).
Insertion sort is stable because the shifting process never moves an element past another element with the same key; the algorithm only shifts elements that are strictly greater.
Interview tip: emphasize that insertion sort achieves O(n) time on nearly sorted arrays, making it the correct choice in practice for such inputs, even compared to more sophisticated algorithms like merge sort or quick sort.
Binary Insertion Sort
A natural improvement to insertion sort replaces the linear scan for the correct insertion position with a binary search. Since the prefix is already sorted, binary search finds the correct position in O(log n) comparisons rather than O(n) comparisons. This variant is called binary insertion sort.
Pseudocode for binary insertion sort: for each index i from 1 to n-1, extract the element at i. Use binary search on the sorted prefix from 0 to i-1 to find the insertion position p. Shift all elements from p to i-1 one position to the right. Place the extracted element at position p.
The improvement in comparisons is significant. Standard insertion sort makes O(n squared) comparisons in the worst case. Binary insertion sort reduces this to O(n log n) comparisons. This is the same number of comparisons as merge sort in the worst case.
However, binary insertion sort still performs O(n squared) shifts because finding the correct position quickly does not reduce the amount of data that must be moved. On arrays with inexpensive comparisons but expensive memory writes, the shift count dominates and binary insertion sort offers no speedup in terms of actual wall-clock time.
Where binary insertion sort genuinely wins is when comparisons are expensive and shifts are cheap. Examples include sorting arrays of objects where the comparison involves deep equality checks, database records compared by a multi-field key, or strings compared character by character.
A worked example: sorting 1,000 strings by lexicographic order using standard insertion sort requires up to 499,500 character-by-character comparisons. Binary insertion sort reduces this to about 10,000 binary search steps, each potentially comparing fewer characters due to early termination in string comparison.
Time complexity: O(n log n) comparisons, O(n squared) shifts, O(n squared) overall. Space complexity: O(1).
Interview tip: when discussing insertion sort optimizations, binary insertion sort is the most impressive one to mention because it touches both algorithmic and systems-level thinking about what the bottleneck actually is.
Insertion Sort in Practice and Shell Sort
Insertion sort is not just a teaching tool. It appears in optimized implementations of other sorting algorithms and in standard library code. The most common pattern is to use insertion sort as a base case within a recursive algorithm. Merge sort and quick sort both have O(n log n) average complexity, but for small arrays the constant factor of recursive overhead makes them slower than insertion sort. Many standard library implementations switch to insertion sort for subarrays of length below 10 to 16 elements.
The Java Arrays.sort method uses a dual-pivot quick sort for primitive types that falls back to insertion sort for small partitions. The C++ std::sort in many implementations uses introsort, which combines quick sort, heap sort for worst-case protection, and insertion sort for small subarrays. Python's Timsort uses insertion sort on each natural run before merging.
Shell sort is a generalization of insertion sort that extends it to achieve better than O(n squared) performance. Instead of comparing adjacent elements, shell sort compares elements that are h positions apart for a sequence of decreasing gap values h. When h is 1, it reduces to ordinary insertion sort. By pre-sorting with large gaps, shell sort reduces the amount of work the final pass must do.
The best-known gap sequence for shell sort produces O(n times (log n) squared) comparisons. With the Ciura gap sequence (701, 301, 132, 57, 23, 10, 4, 1), shell sort performs competitively in practice against O(n log n) algorithms for arrays up to around 100,000 elements and is simpler to implement than merge sort.
A worked example: sorting 1,000 integers with shell sort using the Ciura sequence takes approximately 10,000 comparisons in practice, compared to roughly 250,000 for pure insertion sort on random input.
Time complexity: standard insertion sort O(n squared) worst, O(n) best. Shell sort O(n log n squared) with optimal gaps. Space complexity: O(1) for both.
Interview tip: mentioning that major language standard libraries use insertion sort internally for small subarrays is a strong signal that you understand the difference between theoretical complexity and practical performance.