Sorting II: Merge Sort & Quicksort

The quadratic sorts from last lesson choke on big inputs. Sort a million items with bubble sort and you'll be waiting. The fix isn't a faster swap, it's a smarter strategy. Both algorithms here are built on divide and conquer: break the problem into smaller pieces, solve each piece, and combine the results. That single idea takes sorting from O(n²) down to O(n log n), and the difference at scale is enormous.

Divide and conquer, in one picture

The shape of both algorithms is the same. Split the list, deal with the halves, and stitch the answer back together:

The "sort recursively" step is the same algorithm calling itself on a smaller list, exactly the recursion idea from earlier, with a base case (a list of one element is already sorted) and a recursive case (split and recurse). Where merge sort and quicksort differ is which step does the real work: merge sort does the work while combining, quicksort does it while splitting.

Merge sort: split fully, then merge

Merge sort keeps halving the list until every piece is a single element, and a single element is sorted by definition. Then it walks back up, merging pairs of sorted lists into bigger sorted lists. Merging two already-sorted lists is cheap: compare their fronts, take the smaller, repeat.

Step through it. Watch the list split all the way down, then the sorted pieces fuse back together:

The depth of that split tree is log n levels (you can only halve n about log₂n times before you hit single elements), and each level does n total work merging. log n levels × n work per level = O(n log n). Merge sort is also stable (equal elements keep their original order), which matters when you sort by one field and want ties broken by a previous sort.

Quicksort: partition, then recurse

Quicksort flips the order of operations. Instead of splitting blindly and merging carefully, it does the careful work up front. Pick a pivot, then partition: shove everything smaller than the pivot to its left and everything larger to its right. Now the pivot is in its final position, and you recurse on the two sides. There's no merge step. Once both sides are sorted, the whole thing is sorted, because partitioning already put everything on the correct side.

When the pivot lands near the middle each time, you get the same log n levels of n work, O(n log n) on average, and in practice quicksort is often faster than merge sort because it sorts in place with less data shuffling. The catch is the pivot. Pick badly (say, always the smallest element on an already-sorted list) and your "halves" are lopsided (one element vs. the rest), the split tree degenerates to n levels deep, and you're back to O(n²). Real implementations dodge this with smarter pivot choices (random, or median-of-three).

Merge sort in runnable Python

Here's a clean recursive merge sort, plus a compact quicksort so you can compare them. Run it, then try your own list:

Both are recursive with a one-element base case. Merge sort's effort is in merge (combining), while this quicksort's effort is in the partition (the three list comprehensions that split around the pivot). The <= in merge is what keeps it stable: equal elements from the left half go in first, preserving their order.

Where this leaves you

Divide and conquer is the leap from quadratic to O(n log n): split the problem, solve the halves, combine. Merge sort does its work merging and stays stable at the cost of extra memory. Quicksort does its work partitioning, sorts in place, and is usually faster, as long as the pivot doesn't betray it into O(n²).

You've now seen how to put data in order. Next we use that order to find things fast, halving the search space every step. Next: Binary Search.