The count of the part that was read

Every sort measured so far hands back a complete order: where each of $n$ elements belongs. The sort whose count has no distribution ended on the observation that a great deal of sorting is done for callers who do not want that. A search shows its best ten results. A query asks for the hundred nearest points. A report lists the first page and waits to be asked for the second. Each of these reads a prefix of the sorted order and discards the rest, and each pays, if it calls a sort, for the rest.

A sort’s comparison count has no term in it for this. Merge sort on 65,536 keys makes about a million comparisons whether the caller reads one element or all of them, because the count is a function of the input, and how much of the output is used is not part of the input. The quantity that matters to the caller — call it $k$, the number of elements read — does not appear in any bound a sort is described by.

This page puts $k$ into the count. It takes six ways of handing back the $k$ smallest keys in order, counts each one’s comparisons as $k$ runs from one to all 65,536, and sets them against what no method can do better than.

Two floors, and why they do not add #

There are two easy arguments for a floor, and they bound different things.

Every element not handed back must lose a comparison. To know that an element is not among the $k$ smallest, a method must have seen it compared with something smaller, and each comparison has exactly one loser. So at least $n - k$ comparisons are needed, whatever else is learned. For $k = 1$ this is the familiar fact that finding a minimum of $n$ takes $n - 1$ comparisons.

The answer must be distinguished from every other possible answer. The output is a sequence of $k$ positions, in order, chosen from $n$, and there are $n!/(n-k)!$ such sequences. Each comparison has two outcomes, so at least $\lceil\log_2 n!/(n-k)!\rceil$ comparisons are needed. This is the argument the floor under every comparison sort makes for a full sort, and at $k = n$ it is that floor exactly. The floor moves when the question does made the general point that a floor belongs to a question, and $k$ is a dial between two questions.

It is tempting to add the two, since one counts losers and the other counts bits. At $k = 1$ the sum is $65{,}535 + 16 = 65{,}551$, and a simple scan finds the minimum of 65,536 keys in 65,535 comparisons — sixteen fewer than the sum. The same comparisons that eliminate the losers carry the information, and nothing forces a method to pay for them twice. The floor is the larger of the two, not their sum, and the plates below draw it that way. The checks require the sum to be refused as a floor by a method that goes under it.

The larger of two floors has a weak point, and it is where they cross. For 65,536 keys the loser count starts at 65,535 and falls slowly as $k$ grows; the information count starts at 16 and rises by about sixteen for every element read. They meet near $k = 3{,}900$, at about 61,700 comparisons each, and there each is saying only that the other might be right. Neither floor is close to what any method achieves at that point, and it is worth remembering when the ratios below peak there.

Six ways to hand back the first k #

Sort everything, then read $k$. A flat line at 965,656, fifteen times the floor for any small $k$, and within 1.2% of it at $k = n$, where the question is sorting.

Build a heap, then pop $k$ times. Building a binary heap from the bottom costs about $1.9n$ comparisons — building a heap from the bottom measured 1.87 per element on random input — and each pop sifts a replacement down about $\log_2 n$ levels at two comparisons a level. So the line starts at 123,525 for the smallest element and rises by about 30 comparisons per element read: $1.9n + 2k\log_2 n$. It is the method every priority-queue library supports, and it pays the building cost before the first element whatever $k$ turns out to be.

Select, then sort. Partition around random pivots until the $k$ smallest are separated from the rest, then sort those $k$. Selection by random pivots is expected to cost about $2n$ comparisons when $k$ is small and more as $k$ approaches the middle, and sorting $k$ elements adds about $k\log_2 k$. The method needs $k$ in advance.

Incremental quicksort. Paredes and Navarro’s method partitions only the leftmost unsettled range, and only when the caller asks for the next element, keeping a stack of pivot positions so that no partition is ever repeated. For small $k$ it does the same work as selection. It does not need $k$ in advance, and read to the end it becomes a quicksort, at 1,275,254 comparisons.

Keep the best $k$ while scanning. Walk the input once, holding the $k$ smallest seen so far in a heap whose root is the largest of them; each new element is compared with that root and, if smaller, replaces it. At $k = 1$ this is the minimum scan, and it meets the floor exactly. It is what a database does for a query with a small LIMIT over an ORDER BY, and what a standard library’s “n smallest” function does when $n$ is small.

A knockout tournament. Pair the keys and keep the smaller of each pair, pair the winners and keep the smaller again, and so on up to a single champion — $n - 1$ comparisons to find the smallest. To find the next, remove the champion’s leaf and replay only the matches along its path to the top. The tournament’s line hugs the floor from $k = 1$ to $k = 400$ and is never above any other line on the plate.

A tournament, drawn #

The count can be read off the drawing. The first key costs $n - 1$ comparisons, one per internal node, and that already meets the loser floor exactly: every key but one has lost one match. Each later key costs one comparison per level of the tree above the bottom, which is $\log_2 n - 1$ — fifteen, for 65,536 keys. So the tournament’s count for the first $k$ is very nearly $n - 1 + 15(k-1)$, and at $k = 1{,}000$ that is 80,520 against a measured 80,512, the difference being the few replays that meet an emptied subtree higher up.

Set that beside the two floors. The first key costs exactly the loser floor. Each later key costs fifteen comparisons, and the information floor charges about sixteen bits per key. The tournament pays each later key’s information almost exactly once, and pays the losers once, and the reason it can do both is the one the sum of the floors missed: every one of its early matches is simultaneously a loss for one key and a bit of the order.

Merge sort, paid in instalments #

A tournament that is never told to stop can be read all the way to the last key, and at that point it has produced a full sort.

The tournament’s line ends on the dashed line exactly, and not approximately: 43,953 comparisons against merge sort’s 43,953, and at 65,536 keys, 965,656 against 965,656. The checks require the two to be equal at three sizes, and they are.

The reason is structural. Each internal node of the tournament, replayed every time one of its keys leaves, is a merge of its two subtrees performed one output at a time. It compares the two current front keys until one side is exhausted and then passes the rest of the other side through without comparing anything, which is precisely merge sort’s merge. The tournament is merge sort in which each merge is carried out lazily — a comparison is made only when a key is actually needed above it. Read to the end, every merge is carried out in full and the counts must coincide.

That gives the first plate’s flat line a precise meaning. Sorting 65,536 keys and reading ten makes 965,656 comparisons. The same merges, carried out only as far as the ten keys require, make 65,670. The other 899,986 were spent merging keys nobody read, and the tournament is the proof that none of them was necessary for the first ten.

The heap, read to the end, is a heapsort. It front-loads the cost of building — 7,682 comparisons before the first key — and then pays about nineteen per key, finishing at 1.95 times merge sort. The incremental quicksort, read to the end, is a quicksort with random pivots; its one run here finishes at 1.21 times merge sort, a little under the 1.29 that quicksort’s expected count predicts at this size.

Knowing k in advance, and not #

The six methods divide on a line the count does not show: whether they need to be told $k$ before they start.

Selecting then sorting needs $k$ to know where to partition. The bounded heap needs $k$ to know how large a heap to keep. Sorting everything does not need it, but ignores it. The other three — build-and-pop, incremental quicksort and the tournament — can hand back one key, stop, and resume later when asked for the next, without having done anything on the first call that the caller did not need for that call. That is the interface a caller actually has when it reads a result page by page, or stops scanning search results when it finds what it wanted, and it rules out two of the six.

Among the three that can stop, the instalments plate is also a schedule of payments, and the schedules differ. The tournament charges $n - 1$ for the first key and about fifteen for each key after it. The heap charges about $1.9n$ for the first and about nineteen after. Incremental quicksort charges about $2n$ for the first, on average, and then irregular amounts: a key that lands in a range already partitioned costs almost nothing, and a key that forces a new partition of a long range costs a great deal. What amortised means drew the sawtooth hidden under a dynamic array’s constant amortised append; the same distinction applies here. The tournament’s per-key cost after the first is nearly flat and nearly predictable. Incremental quicksort’s has a low average and a long tail, and a caller that must return each page within a deadline cares about the tail.

What the cheapest count is paid for in #

Every plate on this page counts comparisons, and the tournament wins nearly all of them. It does not win on the other axis this site measures.

A tournament over $n$ keys keeps a tree with $n - 1$ internal nodes, each recording which key won there, beside the keys themselves — about $2n$ slots in all, and it must keep them for as long as the caller might ask for another key. The bounded heap holds exactly $k$ keys and nothing else, which for $k = 10$ is ten slots against 131,071. Build-and-pop and incremental quicksort both work inside the array they were given, with a stack of pivot positions for the second that is short on average. Sorting everything with merge sort needs a buffer of $n$.

So the method closest to the comparison floor is also the one that holds the most, and the method that holds the least — the bounded heap — is the one whose comparison count collapses as $k$ grows and on reversed input. The frontier between time and space drew that trade for full sorts, as comparisons against peak auxiliary space, and found that no sort is best on both. Handing back a prefix has the same frontier with $k$ added to it: at small $k$ the bounded heap is nearly optimal on both axes at once, and as $k$ grows the choice becomes a choice of which axis to lose on. Measuring what an algorithm keeps is the argument that this second axis has to be counted rather than assumed, and on this question it decides between the two best methods on the first plate.

Against the floor #

Three kinds of behaviour are visible.

The tournament is within 2.5% of the floor up to $k = 100$ and within 25% at $k = 1{,}000$. Its worst ratio, 1.97 at $k = 4{,}000$, is at the point where the two floors cross and neither is tight. That peak is a statement about the floor, not about the tournament: nothing on this page says whether a method exists that does much better at $k = 4{,}000$, and the floor’s own kink is the likeliest reason the ratio rises there and falls again by $k = 10{,}000$.

Scanning with a bounded heap is perfect at $k = 1$ and good for small $k$, and then it collapses. Every key that belongs among the best $k$ seen so far costs a sift through the heap, and on random input a key is among the best $k$ seen so far with a probability that grows with $k$. By $k = 1{,}000$ it is at 2.25 times the floor and by $k = 4{,}000$ at 5.4. It is the right method for a small $k$ known in advance and the wrong one for anything else.

The heap and the two selection methods pay a fixed tax of nearly twice the floor before the first key. Building a heap costs about $1.9n$; selection by random pivots costs about $2n$ in expectation, 1.885 times the floor over these sixteen seeds. Both are linear, both are unavoidable in those methods, and both are twice what a tournament pays for the same first key.

What the input does to each #

The plates so far use random input. The methods respond to order very differently.

The tournament does not care. Its count moves by thirteen comparisons across the three inputs, because it plays every first-round match whatever the keys are and then replays one path per key read.

The bounded heap cares more than anything else here. On reversed input every key the scan meets is smaller than everything it holds, so every key enters the heap and costs a sift: 397,550 comparisons, six times its count on sorted input, where no key after the first ten gets in. A method whose cost is a function of how often a new key beats the current best is at the mercy of the order the keys arrive in, and reversed input is its worst case in exactly the sense a worst case ten positions wide called a region.

The heap is cheap on sorted input because a sorted array already satisfies the heap property: building it compares each internal node with its two children, two comparisons, and moves nothing.

The two selection methods are the same on all three, within their sampling error. That is a requirement, not an observation. A pivot drawn at a uniformly random position has a uniformly random rank whatever the arrangement of the keys, so the distribution of a randomised selection’s count cannot depend on the input; a measurement that shows it depending is measuring its random numbers. Seeds that differ by a small constant give a bare shift-register generator first draws that agree with one another, and a selection’s cost is decided almost entirely by its first few pivots, so sixteen such seeds are not sixteen independent runs. Each seed here is mixed through a hash before use. The adversary who knows the seed is about what a stated seed exposes to an opponent; this is the quieter hazard of stating several, which is that they may not be different enough to be several. On average is not a number is why the plates report means over seeds at all.

What to hand a caller who reads a prefix #

If $k$ is not known in advance, use a tournament or anything built like one. It meets the floor for the first key, pays about $\log_2 n$ per key after that, never costs more than a merge sort if the caller reads everything, and does not care what order the input is in. Lazy merge sorts and tournament-based merges in external sorting are the same idea.

If $k$ is known and small, a bounded heap is simplest and nearly optimal — at $k = 10$ it is within 0.6% of the floor on random input — but its worst case is reversed input, and a caller whose data arrives in descending order pays six times as much.

Build-and-pop and select-then-sort are never the cheapest method on these plates, at any $k$. They are the methods most libraries offer for this job, and each pays nearly twice the floor before handing back anything.

And a full sort is the right call only when the caller will read nearly everything — at $k = 40{,}000$ of 65,536 it is still 1.6 times the floor, and the tournament is 1.05. The cost that is the size of the answer found the same shape in a different structure: a method whose cost follows the output wins when the output is small and loses its advantage only as the output approaches everything.

Still open: the floor at the crossing #

Every method on the ratio plate peaks near $k = 4{,}000$, and the likeliest reason is that the floor used there is weak: the larger of two arguments that each ignore what the other counts. The tournament’s cost suggests what a better floor would look like — the first key charged $n - 1$ for its losers, and each later key charged the logarithm of how many keys remain — and floors of roughly that shape, which charge the losers and the later keys’ information together without double-counting the early matches, are known from the analysis of selection.

Computing the best such floor at each $k$ for 65,536 keys, and measuring how far the tournament sits above it at the crossing, would say whether the peak at 1.97 is the floor’s weakness or the method’s, and whether any method can hand back four thousand keys from 65,536 in substantially fewer than 125,388 comparisons. That is a question about the count of the part that was read which neither floor on this page can answer.