Why sorted input changes everything

Ask what an algorithm can learn from one comparison. On unsorted data, a[i] < x tells you about exactly one element: a[i]. On sorted data, the same comparison tells you about every element up to i — all smaller, all disqualified or qualified together, sight unseen. Sortedness is a promise (“order agrees with position”) that converts single comparisons into statements about whole regions, and that conversion is the engine inside a startling fraction of efficient algorithms. This page is about seeing sortedness as stored, spendable work — because once you do, both directions of the trade become obvious.

The spenders

Binary search spends it most famously: one probe eliminates half the array because everything left of a too-small midpoint is also too small. Twenty comparisons search a million elements — but each of those comparisons is doing the work of half a million unsorted ones, cashing in the order. On unsorted data the identical code returns confident nonsense: the eliminations were loans against a promise nobody made.

Two pointers spends it differently: at the ends of a sorted array, the current pair involves an extreme — so a too-small sum condemns the left element against every possible partner at once (it just failed with the largest one available). One comparison, one permanent elimination, n−1 steps total. The whole correctness argument is one sentence long and every word of it leans on sortedness.

Merging spends it wholesale: two sorted lists combine in linear time because each list’s minimum is sitting at its front — no searching, ever. That single fact scales up into merge sort, k-way merges of disk runs, and every “merge intervals / lists / streams” problem.

And a quieter family: duplicates become neighbours (dedup in one pass), closest-pair becomes adjacent-pair (no cross-checking), range queries become two boundary searches, and “is X present?” gets a certificate of absence rather than an exhaustive shrug. Each is the same coin spent in a different shop.

The price of acquiring it

Sorting costs O(n log n), and that number is a genuine floor for comparison-based sorting — provable by counting: n! possible orderings, each comparison splits the possibilities in two, so log₂(n!) ≈ n log n comparisons are needed just to identify the ordering. So the strategic arithmetic is always: does the spending justify the buying?

• One membership query on unsorted data: a linear scan is O(n). Sorting first (n log n) to binary search once (log n) is strictly worse. Don’t buy order you’ll use once.
• Many queries: sort once, then every query is log n instead of n. The purchase amortizes almost immediately.
• Data that arrives over time and must stay queryable: sorting per insertion is ruinous; this is why balanced BSTs and heaps exist — structures that maintain order incrementally at log-cost per update, i.e., sortedness on an installment plan.

Interviews encode this arithmetic constantly. “Find a pair summing to k” — hash map (O(n), no order needed) versus sort-then-two-pointers (O(n log n), O(1) space): which is right depends on whether the input is already sorted and whether memory matters, and saying that is the expected answer. The given “the array is sorted” in a problem statement is never decoration: someone paid n log n for that property, and the setter expects you to spend it.

Nearly sorted is nearly free

Sortedness isn’t binary — the useful measure is inversions, pairs out of order, from 0 (sorted) to n(n−1)/2 (reversed). Adaptive algorithms price by inversions: insertion sort runs in O(n + inversions), which is why it’s the choice for data that’s almost in order (a log with a few late arrivals), and why TimSort — the sort actually inside Python and JavaScript — hunts for pre-existing sorted runs and merges them, sorting genuinely-messy regions only. Run the nearly-sorted preset on the insertion sort visualization and watch the write counter barely move; that counter is the inversion count being paid down, nothing more.

The same measure explains the villains: sorted input is the worst case for a first-element-pivot quicksort (every partition maximally lopsided) and for a plain BST (every insertion extends one chain — the tree degenerates into a list, which the BST visualization’s sorted preset makes painfully visible). Order is stored work, but a few algorithms trip over the storage. Knowing which of your tools spend order, which maintain it, and which are allergic to it is the actual literacy this page is after.

The checklist

When a problem arrives: Is anything sorted already? (Spend it — binary search, two pointers, merging are on the table.) Would sorting unlock a better shape, and do the query counts justify n log n? Does data keep arriving? (Buy maintained order: heap for “just the extreme”, balanced tree for full order.) Is the input nearly sorted? (Adaptive tools get near-linear.) And if you’re about to run a spender — check the promise actually holds, because every algorithm in the spender family fails silently, not loudly, on unsorted input.