Sorting#
Ordering is everywhere in the operator’s day: log lines by timestamp during triage, indicators by score before tasking, hosts by exposure before a campaign brief, evidence by chain-of-custody time during analysis. Sorting is the most-studied algorithmic problem and the language’s built-in sort is almost always the right call. Worth understanding the mechanics anyway, both for predicting how a triage script behaves at scale, and for the cases where not-quite-a-sort (top-k, bucketed, partial) is what the operator actually needs.
The Comparison Lower Bound#
Any comparison-based sort takes at least Ω(n log n)
comparisons in the worst case. Mergesort, heapsort, and
well-implemented quicksort hit this bound; nothing
comparison-based does better. To go faster, you must use
information besides comparisons.
To go faster, you must use information besides comparisons, the data’s range, distribution, or structure.
Comparison Sorts#
The standard catalog of comparison sorts, with worst-case behavior and stability noted. Modern language libraries typically ship Timsort or Introsort (hybrids that pick between strategies based on input structure), which is why “use the built-in sort” is almost always the right answer.
Algorithm |
Best |
Average |
Worst |
Space |
Stable? |
|---|---|---|---|---|---|
Insertion sort |
O(n) |
O(n²) |
O(n²) |
O(1) |
Yes |
Selection sort |
O(n²) |
O(n²) |
O(n²) |
O(1) |
No |
Bubble sort |
O(n) |
O(n²) |
O(n²) |
O(1) |
Yes |
Mergesort |
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 (typically) |
Heapsort |
O(n log n) |
O(n log n) |
O(n log n) |
O(1) |
No |
Shell sort |
depends |
~O(n^1.25) |
O(n²) |
O(1) |
No |
Timsort |
O(n) |
O(n log n) |
O(n log n) |
O(n) |
Yes |
Introsort |
O(n log n) |
O(n log n) |
O(n log n) |
O(log n) |
No |
Insertion sort#
Builds the sorted prefix one element at a time. Tiny constants; the fastest sort for small arrays (~10-30 elements).
for i in 1..n:
key = a[i]
j = i - 1
while j >= 0 and a[j] > key:
a[j+1] = a[j]
j -= 1
a[j+1] = key
Used as the base case in real-world sorts (Timsort, Introsort) for small subarrays.
Mergesort#
Stable, predictable, the typical choice for linked lists and external sorting (more data than fits in memory). O(n) extra space is the cost.
Recursive: split, sort halves, merge.
Quicksort#
Pivot-and-partition. Fast in practice; the worst case is O(n²) on already-sorted (or adversarial) inputs with a bad pivot strategy.
Modern variants.
Median-of-three pivot.
Three-way partition for many duplicates (Dutch national flag).
Introsort, start with quicksort, switch to heapsort if recursion gets too deep. Used by C++
std::sort.
Heapsort#
In-place O(n log n); predictable, but slower in practice than
quicksort due to cache behavior.
Build a max-heap, then repeatedly extract the max into the back of the array.
Timsort#
Real-world hybrid: detects existing runs, merges them, falls back to
insertion sort on small subarrays. The default in Python (list.sort)
and Java (Arrays.sort for objects).
Excellent on partially-sorted data, often O(n) when the input has long sorted runs.
Linear-Time Sorts#
Use information beyond comparisons (the data’s range,
distribution, or fixed-width structure) to break the n log
n lower bound. Practical when keys fit a known range; useful
for fixed-size integers, strings of bounded length, or numeric
ranges.
Algorithm |
Time |
Space |
Constraints |
|---|---|---|---|
Counting sort |
O(n + k) |
O(k) |
Integer keys in known range [0, k) |
Radix sort |
O(d(n + b)) |
O(n + b) |
Fixed-width keys; b = base, d = digits |
Bucket sort |
O(n + k) |
O(n + k) |
Roughly uniform distribution over k buckets |
Practical when keys fit a known range; useful for fixed-size integers, strings of bounded length, or numeric ranges.
Stability#
A sort is stable if it preserves the relative order of equal-key elements. The property matters more than it looks – multi-key sorting becomes a chain of stable single-key sorts; spreadsheets and databases need stable order to be predictable across runs.
Sorting by multiple criteria becomes a chain of stable single-criterion sorts.
Tools (databases, spreadsheets) often need stable behavior to get predictable ordering.
Insertion, mergesort, Timsort are stable; quicksort, heapsort are not by default.
In-Place vs. Out-of-Place#
The space-vs-stability trade. In-place sorts use constant or logarithmic extra memory and tend to be unstable; out-of-place sorts pay an extra O(n) buffer in exchange for stability and predictable behavior on partially-sorted input.
In-place, O(1) or O(log n) extra space (insertion, heapsort).
Out-of-place, O(n) extra space (mergesort, counting sort).
Memory-bound work picks in-place; recoverability and stability often prefer out-of-place.
External Sorting#
When data is larger than memory, you can’t sort the whole
thing in place. The classic external-sort approach is a
two-phase merge: sort chunks in memory, then merge the runs
from disk. Used by databases for large ORDER BY,
sort(1) on big files, and log analytics tools:
Read chunks that fit in RAM, sort them, write each as a sorted run to disk.
Merge the runs (k-way merge with a heap).
The sort step is mergesort or quicksort; the merge step is the characteristic part of external sorting.
Used by databases for large ORDER BY, by sort on big files, by
log analytics tools.
Topological Sort#
Not a “sort” by element value but a related concept worth naming. Topological sort orders DAG vertices so that every edge goes from earlier to later; the standard tool for build systems, dependency resolution, and task scheduling. See Graphs for the algorithm.
The Practical Choice#
The decision flow for “what sort should I actually use?” The built-in is right almost every time; reach for something else only when you have measured a problem and have a specific reason. Custom sorts are an “I’ve measured” decision, not a default.
The built-in sort is the right answer in almost every case.
When you need stability, check that the language’s sort is stable (most modern ones are).
When you have integer keys in a small range, counting / radix sort can beat O(n log n).
When you suspect partially-sorted data, Timsort-style algorithms shine but again, that’s usually the built-in.
Custom sorts are an “I’ve measured and have a specific reason” decision.