Two algorithms, one idea: split in half, solve the halves, put them back together. Recursion is familiar from lesson 5 — there it was a traversal, here it is a sort.

They differ in where the work happens: merge sort does it on the way back up, quicksort on the way down.

Merge sort

MergeSort(items):
    if len(items) <= 1: return a copy
    mid   ← len(items) / 2
    left  ← MergeSort(items[:mid])
    right ← MergeSort(items[mid:])
    return Merge(left, right)

Merge(a, b):
    out ← empty, capacity len(a)+len(b)
    i ← 0; j ← 0
    while i < len(a) and j < len(b):
        cmp.Hit()
        if a[i].Title <= b[j].Title:
            out ← out + a[i];  i ← i + 1
        else:
            out ← out + b[j];  j ← j + 1
        moves.Hit()
    append what is left of a, then of b (each a moves.Hit())
    return out

The splitting compares nothing. All the work is in Merge, and it is linear: every element is touched once. There are log₂ n levels and n work at each — which is where O(n log n) comes from.

One character, and stability lives in it

if a[i].Title <= b[j].Title

That <= means: on a tie, the LEFT half wins. The left half is the one that came earlier in the original slice — so equal items keep their original order.

Write < instead and the sort still works. Tests that only check ordering will pass. But stability is gone — and step 5 shows where that matters.

Quicksort

QuickSort(items):
    if len(items) <= 1: return
    p ← Partition(items, pivotIndex)
    QuickSort(items[:p])
    QuickSort(items[p+1:])

Partition(items, pivotIdx):
    move items[pivotIdx] to the front (moves.Hit() if it moved)
    pivot ← items[0].Title
    i ← 1
    for j from 1 to len(items)-1:
        cmp.Hit()
        if items[j].Title < pivot:
            swap items[i] and items[j];  moves.Hit();  i ← i + 1
    swap items[0] and items[i-1];  moves.Hit()
    return i-1

Here it is the other way round: all the work is in the split, and there is nothing to put back together — once both halves are sorted, the slice is sorted.

And it works in place: no second array, unlike merge sort.

But the pivot is a guess

Partition divides the slice at the pivot. If the pivot is the median you get two equal halves and a depth of log₂ n.

If the pivot is the smallest element, the left side is empty and the right side has n−1 items. And then the same thing again, every level down.

When is the pivot repeatedly the smallest? When you take the first element and the slice is already sorted.

Guess before you read on

In lesson 7, -order sorted was insertion sort's best case: 9,999 comparisons instead of 25 million.

What will the same flag do to a quicksort with a first-element pivot?

Write your guess down. Most people expect sorted input to be less work.