How Sorting Works — Ordering Data Efficiently
Sorting — arranging data in order — is the most studied problem in computer science. Not because sorting itself is exciting, but because sorted data unlocks everything else: binary search becomes possible, duplicates become adjacent, merge operations become efficient, and range queries become trivial.
Databases sort index pages. Search engines sort postings lists. The kernel sorts process lists by priority. Your file manager sorts by name or date. Understanding sorting means understanding the most fundamental algorithmic tradeoff: time vs correctness vs simplicity.
Why Does the Algorithm Matter?
| Algorithm | Best | Average | Worst | Space | Stable |
|---|---|---|---|---|---|
| Bubble sort | O(n) | O(n²) | O(n²) | O(1) | Yes |
| Insertion sort | O(n) | O(n²) | O(n²) | O(1) | Yes |
| Merge sort | O(n log n) | O(n log n) | O(n log n) | O(n) | Yes |
| Quicksort | O(n log n) | O(n log n) | O(n²) | O(log n) | No |
| Heap sort | O(n log n) | O(n log n) | O(n log n) | O(1) | No |
At 1,000 elements, the difference between O(n²) and O(n log n) is 1,000,000 vs 10,000 operations — 100x. At 1 million elements, it's 10^12 vs 2×10^7 — 50,000x. The algorithm matters.
How Does Merge Sort Work?
Merge sort is the simplest O(n log n) sort to understand. It uses divide and conquer:
- Divide — split the array in half.
- Recurse — sort each half (recursively).
- Merge — combine two sorted halves into one sorted array.
The merge step is the key: given two sorted arrays, you can merge them in O(n) by comparing the front elements and taking the smaller one each time.
The recursion splits the array log n times (each split halves the data). Each level of recursion does O(n) total work (merging). Total: O(n log n).
Merge sort is stable — equal elements maintain their original order. This matters when sorting by multiple criteria (sort by name, then by date — stable sort preserves the name order within each date).
The cost: O(n) extra space for the merge buffer. For in-memory sorting, this is usually acceptable.
How Does Quicksort Work?
Quicksort is the most-used sort in practice:
- Pick a pivot — choose an element (commonly the last, first, or median).
- Partition — rearrange so elements less than the pivot are on the left, greater on the right. The pivot is now in its final position.
- Recurse — sort the left and right sub-arrays.
Average case: O(n log n). Each partition divides the array roughly in half, and there are log n levels.
Worst case: O(n²). If the pivot is always the smallest or largest element (already-sorted data with first-element pivot), partitions are maximally unbalanced. Randomized pivot selection avoids this — the probability of consistently bad pivots is negligible.
Quicksort's advantage: it sorts in-place (O(log n) stack space, no O(n) merge buffer). On modern hardware, it's typically faster than merge sort because of better cache performance — the partitioning operates on contiguous memory.
The O(n log n) Barrier
You cannot sort by comparison faster than O(n log n). This is provable: any comparison sort is a decision tree with n! leaves (one for each permutation). The tree's height is at least log₂(n!) ≈ n log n. No algorithm can avoid this many comparisons.
Non-comparison sorts beat this bound by exploiting the data's structure:
- Counting sort — O(n + k) where k is the range of values. Works for integers in a known range.
- Radix sort — O(d × n) where d is the number of digits. Sorts by each digit position.
These are O(n) but only work for specific data types. General-purpose sorting is stuck at O(n log n).
What Sort Does Your Language Use?
Most standard library sorts are hybrid algorithms:
- Timsort (Python, Java, JavaScript, Rust's stable sort) — merge sort + insertion sort. Uses insertion sort for small runs, merge sort for combining them. Exploits partially-sorted data.
- Introsort (C++ std::sort, .NET) — quicksort that switches to heap sort if recursion depth exceeds 2 × log n. Guarantees O(n log n) worst case.
- pdqsort (Rust's unstable sort, Go) — pattern-defeating quicksort. Adaptive: detects already-sorted, reverse-sorted, and other patterns.
You almost never need to implement sorting yourself. But understanding the algorithms explains why sort() is fast, when it might be slow, and why stable vs unstable sort matters.
When Does Sorting Order Matter?
Stable sort preserves the relative order of equal elements. If you sort students by grade and two students have the same grade, a stable sort keeps them in their original order (alphabetical, by ID, whatever it was before).
Unstable sort may reorder equal elements. This is fine when you don't care about the relative order — and unstable sorts are often faster.
In practice: use your language's default sort. If you need stability, use the stable variant (Python and Java sort stably by default; Rust has sort() for stable and sort_unstable() for fast).
Where Does Sorting Appear?
Database query execution — ORDER BY sorts results. GROUP BY often sorts first, then groups adjacent equal values. Sort-merge join sorts both tables before joining.
Search indexing — building an inverted index sorts postings by document ID. Merging index segments is a merge of sorted lists.
External sort — when data doesn't fit in memory, sort chunks that fit, write to disk, then merge. This is how databases sort tables larger than RAM. The merge step is exactly merge sort's merge, but reading from disk.
Scheduling — the kernel sorts runnable processes by priority. Priority queues (min-heaps) are a structure optimized for "give me the next most important item."
Next Steps
- How Searching Works — binary search on sorted data gives O(log n) lookup.
- How Complexity Works — the framework behind O(n log n) analysis.
- How Trees Work — trees maintain sorted order without explicit sorting.