Insertion Sort and Sorted Prefixes

At the start of an outer iteration with index i, positions 0 through i−1 form a sorted prefix containing the same items as those original positions. Save values[i] as the key to insert. Compare backwards through the prefix and shift entries larger than key one place right until the insertion position is available.

The remainder of the array is not assumed sorted. For [5,2,4,1], inserting 2 gives [2,5,4,1], inserting 4 gives [2,4,5,1], and inserting 1 gives [1,2,4,5]. These are completed outer iterations; counting every comparison or shift as a pass would use a different trace convention. State the convention before comparing answers.

Saving key before shifting prevents its original array slot being overwritten before the value is inserted. The inner loop first checks j>=0, then whether values[j]>key. Short-circuit evaluation in the labelled Python example prevents a negative j from being used as an unintended wrapped index. The final insertion writes to j+1.

Using strictly greater-than for shifts preserves the relative order of equal keys in this implementation, making it stable. Replacing the comparison with greater-than-or-equal can move equal items past one another. Stability matters when equal primary keys have an existing secondary order, such as records already sorted by name before sorting by class.

For an already sorted input, each outer iteration performs one unsuccessful key comparison and no shifts, giving linear best-case time. In reverse order with distinct items, insertion i shifts i earlier entries, so the total is 1+2+...+(n−1), quadratic in n. Average time is also quadratic under the usual random-order model.

The algorithm modifies the list in place using a key and indices, so auxiliary space is constant under this model. It can suit small or nearly sorted inputs despite worse large-input growth than merge sort’s standard comparison bound. Test empty and singleton lists, equal values and reverse order. The invariant explains correctness more generally than memorising the result of one example.

def insertion_sort(values):
    for i in range(1, len(values)):
        key = values[i]
        j = i - 1
        while j >= 0 and values[j] > key:
            values[j + 1] = values[j]
            j -= 1
        values[j + 1] = key
    return values

print(insertion_sort([5, 2, 4, 1]))

Attempt the task before opening its worked response. Record each change of state, explain the rule used, and check the result against the original requirements. Code examples labelled Python 3 use that language’s conventions; pseudocode states its own assumptions.