Sorting Algorithms as a Concrete Starting Point

Sorting is the most-studied problem in algorithms, and for good reason. It is fundamental enough that you encounter it in every applied setting (databases, file systems, search engines), structurally rich enough to support a dozen distinct algorithms with different trade-offs, and theoretically deep enough to host one of the cleanest lower-bound proofs in computer science. The story has a moral arc: bubble sort's $O(n^{2})$ horrors give way to merge sort's $O(n \log n)$ elegance, the lower bound proves we cannot do better with comparisons alone, and non-comparison sorts (counting, radix) show that breaking out of the comparison model achieves $O(n)$.

Bubble sort: simple and slow

Repeatedly scan the array; for each adjacent pair, swap if out of order. After one pass, the largest element has "bubbled" to the end. After $n - 1$ passes, the array is sorted. Worst- and average-case time is $O(n^{2})$; best case (already sorted, with early-termination) is $O(n)$. Bubble sort is the canonical pedagogical example of a slow algorithm, useful for teaching, almost never used in practice.

Merge sort: divide and conquer

Merge sort embodies the divide-and-conquer paradigm:

1. If the array has 0 or 1 elements, it is already sorted, return.
2. Split the array in half.
3. Recursively sort each half.
4. Merge the two sorted halves into one sorted array in $O(n)$.

The recurrence is $T(n) = 2 T(n/2) + O(n)$, which by the master theorem (case 2) gives $T(n) = \Theta(n \log n)$, the optimal comparison-sort time. Merge sort is STABLE (equal elements keep their relative order) and is the standard sort in many languages' standard libraries (e.g. Python's Timsort is merge-sort-based with run detection). Its main downside is the $O(n)$ auxiliary space for the merge step.

Quicksort: in-place divide and conquer

Quicksort chooses a PIVOT and partitions the array into elements less than the pivot, equal to it, and greater. Then it recursively sorts the less and greater partitions in place. The average-case recurrence is $T(n) = 2 T(n/2) + O(n) = O(n \log n)$, BUT the worst case (pivot always extreme) is $T(n) = T(n - 1) + O(n) = O(n^{2})$.

In practice, randomised pivot selection (or median-of-three sampling) makes the worst case astronomically unlikely. Quicksort is typically FASTER than merge sort in real systems despite its weaker worst-case guarantee because it has excellent CACHE behaviour and operates in place.

The $\Omega(n \log n)$ lower bound

Theorem. Any comparison-based sorting algorithm requires at least $\Omega(n \log n)$ comparisons in the worst case.

Proof sketch. Model the algorithm as a binary decision tree: internal nodes are comparisons, branches are outcomes (less / equal / greater), leaves are permutations representing final orderings. There are $n!$ possible orderings of $n$ distinct elements, so the tree has at least $n!$ leaves. A binary tree with $L$ leaves has height at least $\log_{2} L$