Insertion Sort

Start here Insertion sort is how most people arrange playing cards in their hand: pick up one card at a time and slide it into the right place among the cards you already hold. It is also O(n²) in the worst case — but unlike selection sort, it becomes very fast when the list is already almost sorted.

The idea — the TA again, Strategy 2 #

1. Move the first paper to a new pile.
2. Take the second paper. Lower marks than the first? Put it below. Higher? Put it above.
3. Take the third paper and insert it in the correct position among the first two.
4. Keep going: insert each new paper into its correct position in the new pile.

The new pile is always sorted; it just keeps getting bigger.

Everyday example: Arranging cards in your hand. You never re-check the whole hand — you just slide each new card left until the card before it is smaller.

Doing it in the same list #

Think of the list as two parts: a sorted part L[:i] on the left and the rest on the right. For each i, take L[i] and swap it leftwards while the item before it is bigger.

Full trace — sort [74, 32, 89, 55, 21, 64] #

Sorted: 21, 32, 55, 64, 74, 89 ✔

The code (iterative) #

def InsertionSort(L):
    n = len(L)
    if n < 1:
        return L
    for i in range(n):
        # Assume L[:i] is sorted
        # Move L[i] to its correct position in L[:i+1]
        j = i
        while j > 0 and L[j] < L[j-1]:
            (L[j], L[j-1]) = (L[j-1], L[j])
            j = j - 1
        # Now L[:i+1] is sorted
    return L

Careful — bug in the lecture slide. The slide writes while(L[j] < L[j-1]): without j > 0. When j reaches 0, Python reads L[j-1] = L[-1] — the last item of the list! The swaps then wrap around the end and keep going, until j becomes so negative that Python stops with IndexError. We ran the slide's code: it crashed on every list we tried, even [1, 2, 3]. Always write while j > 0 and L[j] < L[j-1]:. The j > 0 must come first, so Python stops before reading L[j-1].

Why is it correct? — the invariant #

At the start of step i, L[:i] is sorted.

Inserting L[i] into its correct place keeps L[:i+1] sorted. When i reaches n, the whole list is sorted.

A recursive version #

Another way to think:

1. Recursively sort everything except the last item: L[:-1].
2. Insert the last item L[-1] into that sorted list.

def Insert(L, v):
    # L is sorted; return a sorted list with v added
    n = len(L)
    if n == 0:
        return [v]
    if v >= L[-1]:
        return L + [v]                       # v belongs at the end
    else:
        return Insert(L[:-1], v) + L[-1:]    # insert v into the rest, then put L[-1] back

def ISort(L):
    n = len(L)
    if n < 1:
        return L
    L = Insert(ISort(L[:-1]), L[-1])
    return L

(One lecture slide shows l[-1:] with a small L and else without a colon — both are typos. It must be L[-1:] and else:.)

Trace of Insert([32, 55, 74], 50):

• 50 ≥ 74? No → Insert([32, 55], 50) + [74]
• 50 ≥ 55? No → Insert([32], 50) + [55]
• 50 ≥ 32? Yes → [32] + [50] = [32, 50]
• Build back up: [32, 50] + [55] = [32, 50, 55]; then + [74] = [32, 50, 55, 74] ✔

How long does it take? #

Worst case — the list is in reverse order #

Every new item must slide all the way to the front. Step i makes i swaps.

0 + 1 + 2 + ... + (n − 1) = n(n − 1)/2 → O(n²).

For n = 6: 0 + 1 + 2 + 3 + 4 + 5 = 15.

Best case — the list is already sorted #

Each new item is compared once with the item before it, sees it is bigger, and stops at once. Only about n comparisons → close to O(n)!

Analysis of the recursive version (from the lecture) #

Let T_I(n) = time for Insert on a list of size n, and T_S(n) = time for ISort.

• Insert: T_I(0) = 1, T_I(n) = T_I(n − 1) + 1. Unwinding: T_I(n) = n (it may walk the whole list).
• ISort: T_S(0) = 1, T_S(n) = T_S(n − 1) + T_I(n − 1).

Unwinding: T_S(n) ≈ 1 + 2 + ... + (n − 1) → O(n²).

Selection sort vs insertion sort — real counts #

We counted comparisons on lists of 1000 numbers:

• Selection sort: same work every time.
• Insertion sort: depends on the input — great for almost-sorted lists, about half the work on random lists, same as selection sort on reverse-sorted lists.

In one line: Insertion sort slides each item left into the sorted part; worst case n(n−1)/2 = O(n²), but on an already sorted list only about n steps.

Exam words: insertion sort, sorted prefix L[:i], invariant, j > 0, Insert, ISort, recurrence T_S(n) = T_S(n−1) + T_I(n−1), best case O(n), worst case O(n²).

Quick check #