Algorithms and data structures · Intermediate

Insertion sort: extend a sorted prefix

Trace element shifts to connect inversion counts, adaptive running time and the conditions for stable insertion sorting.

Ask Logeia about this articleTry the three questionsReview your answers

Updated

On this page
  1. Grow the sorted prefix
  2. Trace four elements
  3. Count inversions, not just elements
  4. Binary search does not remove shifts
  5. Ask Logeia about this articleCheck your understanding

Grow the sorted prefix

Insertion sort maintains a sorted prefix of an array and incorporates the next element into it. Save that element as a key, shift larger elements one position to the right, and put the key into the resulting gap. At the start of iteration i, the interval [0,i) is sorted. The suffix need not satisfy any ordering condition yet. This invariant explains both why the next insertion is enough and why a full search for the minimum is unnecessary. Distinguish the key being compared from the records being moved when estimating the cost.

Trace four elements

For [5,2,4,2], save the first 2 and shift 5, producing [2,5,4,2]. Insert 4 past only 5 to obtain [2,4,5,2]. The last 2 moves past 5 and 4, producing [2,2,4,5]. Label the two equal keys by their original positions. If the loop shifts only keys strictly greater than the saved key, the earlier 2 remains earlier. Using a greater-than-or-equal test instead can reverse equal records. Stability therefore comes from the insertion rule, rather than from the name of the algorithm alone.

Count inversions, not just elements

An inversion is a pair of positions whose keys appear in the opposite order from the requested ordering. Shifts in the standard insertion procedure correspond to removing inversions. With I inversions and constant-time comparisons, the work is O(n+I). An already sorted sequence therefore takes linear time, whereas n distinct keys in reverse order have n(n−1)/2 inversions and require quadratic work. The worst-case label O(n²) is correct, but hides useful adaptability. This is one reason insertion sorting is often useful for small or nearly sorted subranges inside a larger sorting procedure.

Binary search does not remove shifts

Binary insertion sort can use binary search to locate the insertion position and reduce comparisons. It must still move elements to open a gap in a contiguous array, so it does not generally become an O(n log n) time algorithm. The ordinary shifting version uses O(1) auxiliary storage, but record-copy costs and expensive comparison functions can change practical trade-offs. Test empty input, a single element, repeated keys and a comparator with a consistent ordering. For a large, thoroughly disordered array, choose a sorting method with a better worst-case growth rate.

Reading and practice are recorded separately in this browser, for each language.

Learn this in order

Build your CS foundations · STEP 10

Choose a learning path