The order equal keys keep

The count somebody chose ranked ten sorting algorithms by six measured quantities and found the orders disagree about 91% of all pairs. Six counters, six rankings, and the conclusion that there is no ranking of sorting algorithms — there are six, and choosing between them is a statement about the data.

There is a seventh quantity, and none of the six can see it. A sort is stable when two records with equal keys come out in the order they went in, and two sorts making identical comparisons, swaps, reads and writes can differ on it. It is the property a caller asks for when sorting a table by one column after sorting it by another, and it is the reason the standard library of nearly every language ships the sort it does.

This page measures it: which sorts have it, what it is worth in the currency the other six use, and what it costs to buy from a sort that does not.

Making the property visible to a counter #

The difficulty is that stability is a statement about records and every count on this collection is a statement about an array of numbers. Counting instead of timing is the instrument: an array that increments a tally each time it is read, written, compared or swapped. It has no notion of a record with two fields, so it cannot see whether two records with the same key came out in the order they arrived.

The repair is to put the arrival position into the number and take it back out afterwards. Each record becomes $\text{key} \times M + \text{position}$ for an $M$ larger than the array, and the sort is handed a comparator that divides by $M$ before comparing — so it sees genuine ties and its counts are exactly the counts it would make on bare keys, and the positions are still there in the sorted array to be read off. The adversary who knows the seed used the same door for a different purpose: a comparison sort is defined as one that learns about its input only through the comparator, so replacing the comparator is the one intervention that cannot change what the algorithm is.

Every plate below is that measurement, and the thing to notice about it is that it adds a seventh count to the six. It is not a count of operations; it is a count of the answer — how many pairs came out wrong — and it is the only quantity on this collection that measures what a sort produced rather than what it did.

Who moves equal keys #

Each record is a key and its arrival position, and the sort is given a comparator that reads the key only — so it sees genuine ties, its counts are the counts it would make on bare keys, and afterwards the positions say what it did with them.

Four and four, and the division does not follow any of the six counts. Merge sort at 42,325 comparisons and bubble sort at 8,250,057 are both stable; heapsort at 77,248 and selection sort at 8,386,560 are both not. The property is decided by whether the algorithm ever moves an element past an equal one, and that is a question about which positions it swaps rather than about how many.

The two quadratic sorts are the clearest pair. Bubble sort compares adjacent elements and swaps only when strictly out of order, so an equal pair is never exchanged; selection sort finds the minimum of the remaining range and swaps it into place, and that swap throws whatever was in the way to the far end of the range, past every equal element between. Same asymptotic class, same order of comparisons, opposite answers, and the reason is one line of each.

The ties, and how many there are #

The comparisons that decide stability are the ties, and how many there are is a property of the data rather than of the sort.

At two distinct keys three comparisons in four are ties; at a thousand, one in five. That is the axis every statement about stability lives on, and it is worth being explicit that it is not the axis a sort is usually measured on. A benchmark of random distinct keys has almost no ties and cannot distinguish a stable sort from an unstable one by any count at all — the two make the same comparisons, the same swaps, and produce the same array.

Which is why the question is usually settled by reading an implementation rather than by measuring. This page’s whole method is a way of making the property visible to a counter: give the records tags, and the counter sees what happens to ties instead of being told.

Quicksort’s 97.5% at sixteen distinct keys is the number to carry into the sections below. Nearly every comparison a two-way partition makes on data with few distinct keys is between two equal keys, which means nearly every comparison it makes decides nothing about where anything goes — and the sort still has to make it. The pairs it leaves out of order barely move across the whole sweep, from 705 at two distinct keys to 1,533 at a thousand, because the number of equal pairs available to misplace rises and the chance of misplacing each one falls.

Stability is a rule, not a structure #

The cheapest demonstration of that is merge sort with one character changed.

Forty comparisons apart, one in a thousand, and one of them is stable and the other is not. Nothing structural distinguishes them: the recursion is the same, the buffer is the same, the merge is the same loop with < where the other has ≤.

So stability is not a property a sort has by being the kind of sort it is. Merge sort is stable because its merge prefers the left half on a tie, and a merge that preferred the right would be a merge sort that is not. The same is true of the other three on the first plate: insertion sort stops shifting when it meets an equal element, bubble sort swaps only on strict inequality, and each would lose the property if it did not.

That also explains what happens to the counts. Taking the right half on a tie makes the merge take a different branch on 23,000 comparisons, which changes the run lengths slightly and the comparison count by 0.09%. The property costs nothing and the choice is invisible in every count — which is exactly why it has to be specified rather than measured.

Buying it from a sort that does not have it #

A caller who needs stability and an unstable sort has a standard repair: decorate each record with its arrival position and compare the pair lexicographically. Ties on the key are broken by the position, no two decorated records are equal, and any correct sort then produces the stable order.

The space is the same for every sort — 4,096 words of tag, one per record, which for eight-byte records is a fifty per cent increase in the data — and the comparisons are not the same at all.

Five sorts pay nothing. Insertion, selection and bubble sort make a number of comparisons that does not depend on the answers; merge sort and its hybrid take the same branches on the decorated keys as their tie rule already took. For these, stability by decoration costs $n$ words and nothing else.

Heapsort pays eleven per cent and Shellsort sixty-four. Both use ties: a sift that stops on an equal element does less work than one that does not, and breaking every tie takes that away.

And quicksort is paid ninety-five per cent. That is the finding worth the page.

Why decorating makes quicksort twenty times faster #

Median-of-three quicksort on 4,096 records over eight distinct keys makes 1,071,653 comparisons. Decorated, it makes 54,737 — a factor of 19.6.

The mechanism is the one three-way partitioning exists for. A two-way partition splits the range into “less than the pivot” and “not less”, and a range in which most elements equal the pivot goes almost entirely into one side. With eight distinct keys among four thousand records, every pivot equals about an eighth of its range, and the partition is repeatedly lopsided for a reason no pivot rule can fix — median-of-three picks a pivot in the middle of the values, and the middle value still has five hundred copies.

Decorating removes that. The keys become distinct, every pivot splits its range near the middle, and quicksort runs at its expected $1.39 n \log_2 n$.

So the decoration is doing two things at once and only one of them was asked for. It buys stability, which is the point; and it removes duplicate keys, which is a repair for a pathology quicksort has and the other sorts do not. The 0.05× is not a fact about stability. It is a fact about how badly a two-way partition handles ties, measured by an experiment that happened to remove them.

That is worth stating carefully because the arithmetic invites the wrong conclusion. A caller choosing quicksort for data with few distinct keys should not decorate in order to go faster; they should use a three-way partition, which costs no extra space and removes the same pathology. The decoration is the right repair for stability and an accidental repair for something else.

The four that ship #

The sorts above are the textbook ones. The four a real standard library runs make the same division, and they make it in a way that decides something.

pdqsort is the cheapest of the four on this data and the dearest as soon as stability is asked for. Undecorated it makes 22,588 comparisons against Timsort’s 28,489 — twenty-one per cent fewer. Decorated it makes 53,872 against Timsort’s unchanged 28,489 — eighty-nine per cent more.

The reason is that pdqsort’s speed on this input is its handling of ties: it detects ranges of equal elements and skips them, which is the partitioning repair the previous section said quicksort needs and pdqsort has. Decorating makes every key distinct and there is nothing left to detect, so the repair cannot fire and the sort pays the ordinary price. A sort optimised for duplicate keys is a sort that loses everything when the duplicates are taken away, and taking them away is exactly what decoration does.

So a library choosing between them faces a question with no single answer. If the caller does not need stability, pdqsort is twenty per cent cheaper. If the caller needs it — and a library sorting objects by a field usually assumes they might — Timsort is forty-seven per cent cheaper than the alternative and needs no tag. The sort the library ships is the page that measures what those libraries actually chose; this is one of the numbers behind the choice, and it is not a number any of the six counts reports.

What is being counted, and what a caller pays #

Three quantities separate here and only the first is what the earlier pages count.

Comparisons move between 0.05× and 1.64× and the direction depends on whether a sort was exploiting ties or suffering from them.

Space is $n$ words, for every sort, and that is usually the binding cost. The exchange rate nobody wrote down measured what happens to the ranking when a record grows: selection sort goes from second-worst of seven at four bytes a record to best of seven at five hundred and twelve, because its data movement is what a large record makes expensive. A tag is four or eight bytes on every record, and on small records it is the difference between a cache line holding eight of them and holding five.

And the comparator’s own cost. A lexicographic comparator reads a second field on every tie, which on this data is between a fifth and 99% of all comparisons. Every count on this collection charges one unit per comparison, and the comparison that is not one comparison is the standing argument that the unit is a choice. Here the choice hides a term that the tie share makes large exactly where stability matters most.

What is not measured here #

Uniform keys. The records draw their keys uniformly from the distinct values, so every key has about the same number of copies. A distribution with one very common key and a long tail — which is what real data looks like — would have the same tie share concentrated in different places, and quicksort’s collapse would be worse.

One repair for stability. Decoration is the general one. Particular sorts have cheaper ones: heapsort can be made stable by a different sift rule at some cost in moves, and a quicksort can be made stable by partitioning out of place into a buffer, which is $n$ words again and a different $n$ words. Neither is measured.

Comparisons, not comparator calls. A decorated comparison that reads only the key is counted the same as one that reads the key and the tag. The tie counts are reported so a reader can apply their own weighting, and no plate applies one.

Pairs out of order, not a distance. A sort that moves one record past two thousand equal ones and a sort that swaps two thousand adjacent equal pairs both report two thousand. What a caller notices is usually the first, and a worst case ten positions wide is the page that argues a count of misplacements is a poor description of how far an arrangement is from the one wanted.

No deletions from the definition. Stability is defined here on a single sort of a single array. The reason callers want it is that it composes — sorting by one key and then by another leaves the first as a tiebreak — and nothing here measures a composition.

One size. Four thousand records throughout. The tie share at a fixed number of distinct keys rises with $n$, since more records share each key, so every effect on this page is larger on a larger table and the eight-distinct-key column is a mild case rather than an extreme one.

One record shape. The tag is a word and the key is a word. Nothing about the plates changes if the record is a hundred bytes; what changes is which of the three costs above dominates, and it is the second.

Still open: the sort that is stable and does not pay for it #

Every stable sort on the first plate uses extra space or quadratic time. Merge sort’s $n$-word buffer is exactly the space decoration would have cost, so a caller who wanted stability paid for it either way; insertion and bubble sort are in place and quadratic. The two sorts here that are fast and in place — heapsort and quicksort — are both unstable, and nothing on this page says whether that is a coincidence.

It is not known to be. In-place stable merging is possible in $O(n \log n)$ comparisons with $O(1)$ extra space, by algorithms that are considerably more intricate than a merge and are not what any library ships. The question a measurement can answer is what the intricacy costs in the currencies this collection counts.

The measurement that follows implements one of them — the block-swapping in-place merge that a symmetric rotation gives — and sets it against the buffered merge on the same records: comparisons, moves, peak auxiliary space, and equal pairs moved. The prediction from the literature is that the comparisons are within a small factor and the moves are several times more, which would put it on the frontier the frontier between time and space drew rather than above it — and would say that the reason libraries buffer is a constant rather than a class.