Sorting I: The Simple Sorts

Insertion sort: how you sort cards

Insertion sort is exactly how most people sort a hand of cards. Keep the left part of the array sorted; take the next element and slide it leftward past everything larger until it drops into place. After each step, the sorted region grows by one.

Sorting [ 5  2  4  1 ] by insertion (| marks end of sorted region):

  [ 5 | 2  4  1 ]   take 2, slide past 5     -> [ 2  5 | 4  1 ]
  [ 2  5 | 4  1 ]   take 4, slide past 5     -> [ 2  4  5 | 1 ]
  [ 2  4  5 | 1 ]   take 1, slide to front   -> [ 1  2  4  5 | ]
  done.

void insertionSort(int a[], int n) {
    for (int i = 1; i < n; i++) {
        int key = a[i], j = i - 1;
        while (j >= 0 && a[j] > key) { // slide larger ones right
            a[j + 1] = a[j];
            j--;
        }
        a[j + 1] = key;               // drop key into the gap
    }
}

Selection and bubble, briefly

Selection sort repeatedly scans the unsorted part for the smallest element and swaps it to the front. Bubble sort repeatedly walks the array swapping adjacent out-of-order pairs, so big values "bubble" to the end. All three are simple nested loops.

void selectionSort(int a[], int n) {
    for (int i = 0; i < n - 1; i++) {
        int m = i;                       // index of smallest in a[i..]
        for (int j = i + 1; j < n; j++)
            if (a[j] < a[m]) m = j;
        std::swap(a[i], a[m]);           // put it at position i
    }
}

One thing selection sort gets right: it does at most n−1 swaps total — fewer than the others. If swapping is far more expensive than comparing (large records), that can actually matter. Bubble sort is the slowest of the three in practice and is mostly kept around as a teaching example, not for real use.

Why all three are O(n^2)

Each does, in the worst case, about n passes that each touch up to n elements — a nested loop, so O(n^2) comparisons. Double the input and the work roughly quadruples. That's fine for n in the dozens, painful for n in the millions.

Insertion sort has a lovely best case: on already-sorted (or nearly-sorted) data the inner `while` never moves anything, so it runs in O(n). Selection sort always does the same n^2/2 comparisons regardless of input.

So why still teach them?

1. They're easy to write correctly — fewer places for bugs to hide than in the fast sorts.
2. Insertion sort is genuinely best for small arrays and nearly-sorted data — real libraries switch to it for tiny subarrays.
3. Their loop invariants and pass-by-pass behavior build the intuition merge sort and quicksort will lean on.

Next guide we break the O(n^2) ceiling with merge sort and quicksort — both built directly on the divide-and-conquer idea from the last guide.