Sorting Strategies

Putting Things in Order

Sorting arranges a collection into order, and it is one of the most studied problems in computing because so much else (searching, deduplication, grouping) becomes easy once data is sorted.

The simple sorts are quadratic, $O(n^2)$, and easy to understand:

• Bubble sort repeatedly swaps adjacent out-of-order elements, letting large values "bubble" to the end.
• Selection sort repeatedly finds the smallest remaining element and places it next.
• Insertion sort builds a sorted prefix, inserting each new element into its correct place — and is genuinely fast on nearly-sorted or small inputs.

The efficient sorts are $O(n \log n)$ and are what real systems use for large data:

• Merge sort recursively splits the list in half, sorts each half, and merges the two sorted halves — a clean divide-and-conquer, always $O(n \log n)$, and stable.
• Quicksort partitions around a pivot (smaller elements left, larger right) and recurses; it is $O(n \log n)$ on average and very fast in practice, though a bad pivot gives an $O(n^2)$ worst case.
• Heapsort builds a heap and repeatedly extracts the extreme, guaranteeing $O(n \log n)$.

A key property is stability: a stable sort preserves the relative order of elements that compare equal. This matters when sorting by one field while wanting ties broken by a previous order (sort by last name, keeping first-name order within ties). Merge sort is stable; the usual quicksort is not.

There is a proven lower bound: any comparison-based sort needs at least $\Omega(n \log n)$ comparisons in the worst case — so $O(n \log n)$ is the best a general comparison sort can do.

Common pitfall: assuming the "best" sort is always the fastest asymptotic one. For small or nearly-sorted inputs, a simple $O(n^2)$ insertion sort can beat an $O(n \log n)$ sort because of lower constant overhead — which is why real library sorts switch to insertion sort for small sub-arrays. Match the sort to the input.

A merge-sort recursion tree: a list splitting into halves down log n levels, then accent merge-arrows combining sorted runs back up, with a side note that each of the log n levels does O(n) work.

$$\text{merge sort} = O(n \log n)$$