Bubble and insertion sort

Start here: what this lesson is for

Sorting is the first place the cost ladder from chapter 1 stops being theory. Two algorithms in this lesson do exactly the same job, and one of them is a thousand times slower on a thousand items - not because it is badly written, but because of its shape.

You will almost certainly never write these two sorts in real work. That is not the point. They are small enough to hold in your head completely, which makes them the right place to feel why quadratic growth is fatal - a feeling you will carry into every later chapter.

There is also a genuine surprise waiting: one of these 'slow' sorts is inside the sorting library you already use, and the last lesson of this chapter shows exactly where and why.

You already know how to sort

Pick up a hand of playing cards, dealt in a jumble. Nobody has to teach you what to do next: you look along the hand, spot a card that's out of place, and slide it back to where it belongs. Do that until nothing is out of place, and the hand is sorted.

That's it. Every sorting algorithm in this chapter is a precise version of something you already do by instinct. What differs is how much work each one spends getting there - and in chapter 1 you learned to count that work rather than guess at it.

We start with the two slow ones. Not because you'll use them, but because they are small enough to hold in your head completely, and because feeling why they're slow is what makes the fast ones feel inevitable.

Bubble sort: walk, compare, swap

Bubble sort is the one almost everyone meets first. Walk along the array comparing each pair of neighbours, and whenever the left one is bigger, swap them. One full pass drags the largest value all the way to the end - it 'bubbles' up. Then do it again for what's left.

After the first pass the biggest value is home and never needs looking at again, so each pass can stop one step earlier. And if a whole pass makes no swaps at all, the array was already sorted and you can stop immediately.

void bubbleSort(int[] a) {
    for (int pass = 0; pass < a.length - 1; pass++) {
        boolean swapped = false;
        // each pass parks one more value at the end, so shrink the range
        for (int i = 0; i < a.length - 1 - pass; i++) {
            if (a[i] > a[i + 1]) {
                int tmp = a[i];
                a[i] = a[i + 1];
                a[i + 1] = tmp;
                swapped = true;
            }
        }
        if (!swapped) return;   // nothing moved: it is already sorted
    }
}

int[] a = {5, 1, 4, 2, 8};
bubbleSort(a);
System.out.println(Arrays.toString(a));

pass 1:  [1, 4, 2, 5, 8]   (8 bubbled to the end)
pass 2:  [1, 2, 4, 5, 8]   (5 parked)
pass 3:  no swaps -> stop early
[1, 2, 4, 5, 8]

Insertion sort: how you actually sort cards

Insertion sort is closer to what your hands do. Treat the left of the array as a sorted region that starts as just the first card. Take the next card, slide it left past everything bigger than it, and drop it into place. Repeat. The sorted region grows by one each time until it's the whole hand.

The inner loop doesn't swap repeatedly - it shifts bigger values one slot right to open a gap, then writes the held value into the gap once. That's roughly half the memory traffic of bubble sort's swapping, and it's why insertion sort is meaningfully faster in practice despite having the same Big-O.

Its real superpower is what happens on data that's nearly sorted. If every card is already close to home, the while loop barely runs, and the whole sort collapses towards O(n). Real-world data is very often nearly sorted, which is why insertion sort is still inside the sorting library you use every day - you'll see exactly where in the last lesson.

void insertionSort(int[] a) {
    for (int i = 1; i < a.length; i++) {
        int key = a[i];        // the card in your hand
        int j = i - 1;
        while (j >= 0 && a[j] > key) {
            a[j + 1] = a[j];   // slide bigger values right
            j--;
        }
        a[j + 1] = key;        // drop it into the gap
    }
}

int[] shuffled = {5, 1, 4, 2, 8};
int[] nearly   = {1, 2, 4, 5, 8};   // already in order

shuffled  [1, 2, 4, 5, 8]   shifts: 5
nearly    [1, 2, 4, 5, 8]   shifts: 0   <- the while loop never ran

Why quadratic hurts

Both sorts have a loop inside a loop, and chapter 2 already told you what that costs: for n items you do roughly n squared / 2 comparisons. Doubling the input quadruples the work.

At small sizes nobody notices - and that matters more than it sounds, because it's exactly why real libraries hand small chunks to insertion sort. At large sizes it becomes impossible, not slow.

Selection sort, and why it never gets lucky

There is a third quadratic sort worth meeting, because it makes a point the other two cannot. Selection sort walks the unsorted region, finds the smallest value, and swaps it into place. Then it does the same for the remaining region.

It has one genuine virtue: it makes at most n swaps, one per position. When writing is far more expensive than reading - flash memory, or moving large records - that matters, and selection sort can be the right choice.

But it has no best case at all. Bubble sort escapes early when a pass makes no swaps; insertion sort barely works on nearly-sorted data. Selection sort must scan the entire remaining region to be sure it has found the minimum, so it does the same n squared / 2 comparisons on sorted, reversed and random input alike.

That is the lesson: two algorithms can share a Big-O and still behave completely differently on real data. Big-O is the ceiling, not the whole story.

void selectionSort(int[] a) {
    for (int i = 0; i < a.length - 1; i++) {
        int smallest = i;
        for (int j = i + 1; j < a.length; j++) {   // ALWAYS scans the rest
            if (a[j] < a[smallest]) smallest = j;
        }
        int tmp = a[i]; a[i] = a[smallest]; a[smallest] = tmp;
    }
}

1,000 items - comparisons made

               random     sorted     reversed
bubble        499,500        999      499,500
insertion     249,750        999      499,500
selection     499,500    499,500      499,500   <- never varies

swaps made
bubble        249,750          0      249,750
selection         999        999          999   <- always n-1

Recap: what this chapter actually taught

Three algorithms, one shape, and a set of distinctions that matter far more than the code.

Comparisons and swaps are different costs. Selection sort makes the fewest swaps and the most comparisons. Which one you care about depends on what your data costs to move.

Adaptivity is real and unmeasured by Big-O. Insertion sort collapses toward O(n) on nearly-sorted data, and real data is very often nearly sorted. That single property is why it survives inside modern libraries.

Small inputs are their own regime. Below a few dozen elements these sorts genuinely beat the clever ones, because the constants Big-O discards are still real. Production sorts exploit this by handing small chunks to insertion sort.

The next two lessons take the same job and change the shape rather than the details - and that is where the thousand-fold difference comes from.