Permuting is the harder problem here

Take an array and a permutation of its indices, and produce the rearranged array. Nothing is compared. Nothing is decided. Every element’s destination is written down in advance, and the whole job is to move each one to where it is already known to belong.

In the model this collection used for its first several fields, that is the definition of an easy problem. It costs $\Theta(n)$ — one read and one write per element — and sorting the same array costs $\Theta(n \log n)$, so permuting is cheaper by the logarithm and the gap widens with $n$. Anybody would call sorting the harder of the two.

Here it is the other way round, and not by a little.

The reversal is worth stating carefully before it is measured, because there are two different claims nearby and only one of them is true. The false one is that permuting has become expensive in some absolute sense: it has not, and the last plate on this page shows it costing less than three transfers per block when the data fits. The true one is that the separation between permuting and sorting, which is the whole reason anybody distinguishes them, does not survive the change of unit. In the model where an access costs one, the two problems are a logarithm apart. In the model where a transfer costs one, they are a constant apart, and which constant depends on parameters neither problem statement mentions.

Why moving one element costs a whole transfer #

The naive method is two lines. For each output position $i$, read the source element at $\pi(i)$ and write it to $i$. The writes are sequential — they walk the output in order — so they cost $n/B$ in total and are not the problem. The reads are the problem.

$\pi$ is a permutation, so its values are scattered. A read of $\pi(i)$ brings in the whole block containing that element, which is $B$ elements, of which one is wanted. The other $B-1$ are wanted eventually, but “eventually” means at some other point in the output, chosen uniformly at random, and the block will have been evicted long before then. So the read costs one transfer and delivers one useful element, and $n$ of them cost $n$.

That is the identical failure one access, eight kilobytes opened this field with — a factor of $B$ between the same accesses in a good order and a bad one — arriving in a problem whose whole content is that the order is fixed by somebody else. There is no freedom to reorder the reads without knowing something about $\pi$, and the algorithm is not permitted to know anything about $\pi$ that it has not read.

The measured numbers are slightly better than $n$, and the gap is worth naming rather than rounding away. At $n = 65{,}536$ and $B = 64$ the naive method costs 63,601 transfers rather than 65,536, because a memory of sixty-four blocks does hold on to a few of them long enough for a second element to be wanted. That is a 3% saving and it does not grow: at $B = 128$ the same measurement gives 62,745, still within 5% of $n$. The saving from residency is a constant that a larger block does not increase, which is the opposite of every other result in this field and is worth having explicitly.

Nothing about the algorithm is at fault, and it is worth being clear that no cleverness rescues it. An implementation could sort the reads into address order and issue them sequentially — but then the writes are scattered instead, and the writes are charged too. It could hold a buffer of pending elements — but a buffer that helps must hold a constant fraction of the array, which is the case where the whole thing fits and the problem is not this problem. The one move that works is the one the next section takes, and it works by giving up on moving elements at all until it can move them in bulk.

Sorting by destination, and why it is cheap #

The alternative does something that looks obviously wasteful. Instead of moving elements, it builds pairs — destination, element — and sorts them by destination. Then a single sequential pass writes the sorted elements out in order.

Every step of that is a scan or a merge, and both are sequential. Sorting what will not fit established the cost: run formation reads and writes the whole file once, and each merge pass reads and writes it once more, so the total is $2\lceil n/B \rceil (1 + \lceil \log_{M/B}(n/B) \rceil)$. At $n = 65{,}536$, $B = 64$ and $M = 4{,}096$ that is two passes and 4,096 transfers.

Fifteen times cheaper than moving the elements individually, for an algorithm that does strictly more work in every other unit the site counts. It performs about a million comparisons the naive method does not perform. It reads and writes each element four times rather than twice. Every counter that predates this field ranks it second, and every one of them is measuring something that is not what the machine is doing.

The reason this feels wrong is worth naming, because it is a habit rather than an error. Every count this collection took before the block that is not a block charged one unit per element touched, and under that convention doing more to each element is always worse. The transfer count breaks the link between how often an element is touched and what touching it costs — a touch inside a resident block is free and a touch outside one costs $B$ — so the quantity to minimise stops being work and becomes how often the work leaves memory. Sorting touches each element more times and leaves memory fewer times, and only the second is charged.

Where the crossing is, and it is not where the arithmetic first suggests #

The naive method costs about $n$. The sort costs about $2(n/B)(1+p)$ with $p$ merge passes. Setting them equal gives $B = 2(1+p)$, which at two passes is $B = 4$: below four elements to a block, moving them one at a time wins.

The measurement agrees, which is worth saying because it need not have. At $B = 3$ the naive method costs 107,205 transfers and the sort 109,250; at $B = 4$ they are 95,843 and 65,536. The crossing is exactly where the one-line calculation puts it, and it is not sensitive to $n$ — the same sweep at a quarter of the size crosses in the same place.

The agreement is also a check on the simulation rather than a coincidence, and it is the kind this field relies on. The naive method’s cost and the sort’s cost are computed by two pieces of machinery with nothing in common — one replays a scattered access sequence through a resident set, the other runs a real merge — and the closed forms for both were written down before either was measured. Two independent routes landing on the same crossing is the same sort of evidence fitting a class to measurements demands before granting a class: agreement between things that could have disagreed.

A block of three or four elements is not a hypothetical. It is what a cache line looks like for objects of sixteen or thirty-two bytes, and it is roughly the regime in which the naive permutation is the right answer. Above it — every disk, every SSD, every page — the sort wins, and the margin grows linearly in $B$.

So the model does not say that permuting is expensive. It says that permuting costs the same as sorting, and the reason it looks like a reversal is that the random-access model says something much stronger about their difference than it can support.

It is worth being exact about how far that goes, because a plate drawn at one memory could be mistaken for a general claim. Give the model a memory twice the size of the array — every block resident, nothing ever evicted — and the naive method is still the dearer of the two, by a factor of exactly 1.5 at every block size. The reason has nothing to do with locality: an out-of-place permutation reads a source array and writes a destination array, so it touches twice the address space and pays three scans where a sort that rearranges in place pays two. The separation does not return when the pressure is removed. What returns is the ability to ignore it, since at that memory both costs are small.

It is also the reason the previous rung’s dial exists. One dial between two structures turns a structure’s insertion cost from a whole block per key into a fraction of one by batching, and the batching works for exactly the reason the sort works here: several elements that will end up near each other are moved together, so the transfer they share is amortised across them. Two different problems, one mechanism, and in both cases the thing being defeated is that a scattered write costs a block.

The bound, and which half of it is proved here #

There is a theorem behind this and it is worth stating precisely, because the measurements above are consistent with it rather than a demonstration of it.

Aggarwal and Vitter proved in 1988 that permuting $n$ elements in this model requires

$$\Omega\left(\min\left(n,\ \frac{n}{B}\log_{M/B}\frac{n}{B}\right)\right)$$

transfers. The minimum of the two is exactly the pair of methods above: the left-hand term is moving elements one at a time, the right-hand term is sorting, and the theorem says that no third method beats whichever of them is smaller. That is a lower bound on the problem, not a description of an algorithm, and it is the kind of statement the floor under moving data is about.

Nothing on this page proves it. What the plates do is measure two algorithms and find them where the bound says the best possible method sits, which is evidence that the bound is tight and no evidence at all that it is true. This site has been careful about that distinction since its first floor, and the reason to be careful is that a measurement agreeing with a bound is exactly what a measurement of a worse algorithm would look like if the bound were loose.

The interesting consequence is a negative one. In this model, permuting and sorting are the same problem up to a constant, for every parameter setting except the narrow one where blocks hold a handful of elements. In the random-access model they differ by $\log n$ and that difference is the reason radix sort, counting sort and every other non-comparison method exists. Here that whole line of reasoning collapses: a method that avoids comparisons cannot get under the permutation bound, because arranging the output is a permutation, so it cannot beat comparison sorting by more than a constant either.

The collapse is worth following one step further, because it retires an argument rather than merely qualifying it. In the random-access model, the reason to reach for a non-comparison sort is that $\Theta(n)$ beats $\Theta(n\log n)$ and the beating is asymptotic. If both are $\Theta((n/B)\log_{M/B}(n/B))$ in transfers, then the choice between them stops being about classes and becomes about constants — the number of passes each makes at the actual $M$ and $B$, and how well each one’s inner loop uses a resident block. That is a measurement rather than a theorem, and it is one this collection is equipped to take: the count somebody chose is exactly the argument that a ranking depends on which quantity is counted, applied to sorting algorithms, and this field supplies a seventh quantity for it to be re-run against.

What this does to the non-comparison sorts #

The collection has a floor for comparison sorting — $\log_2(n!)$ comparisons, computed exactly in the floor under every comparison sort — and it has always had the standard escape beside it: an algorithm that does not compare is not bound by it. Radix sort reads digits. Counting sort reads values as indices. Both are linear, and both are correct.

In transfers, neither is. A radix sort over $n$ keys in $d$ passes performs $d$ distributions, and a distribution writes each element to one of $R$ output streams — which is $R$ blocks that must all be resident, or the writes become scattered and cost one transfer each. So radix sort in this model is $d$ scans when $R$ blocks fit in memory, and $d \cdot n$ when they do not; and $d$ is $\log_R(\text{key range})$, which is the same logarithm the merge sort has, with $R$ where $M/B$ was.

That is the same bound with the letters renamed, and it is a specific instance of the general statement: the escape from the comparison floor does not carry over, because the floor here is on movement rather than on information. A counting argument about how many orderings a comparison can distinguish says nothing about a machine that has to physically relocate the data, and the physical relocation is the whole cost.

Five problems, two models, and where they part company #

It is worth setting the disagreement beside the agreements, because a model that disagreed everywhere would be a different subject rather than a second opinion.

The first four rows are the same statement in two units. A scan is linear both ways and the constant changed. A binary search is logarithmic both ways and the argument of the logarithm changed. A B-tree search is a redesign that the first model cannot see the point of, because in accesses it is no better than a binary search and in transfers it is the difference between thirteen and two. A comparison sort’s shape survives entirely, with the base of the logarithm moving from two to the number of blocks that fit in memory — which is the staircase rather than a slope, and is the one place the second model introduces a discontinuity the first has not got.

The last row is the only one where the two models rank two problems differently. That is a small enough disagreement to be worth taking seriously and a large enough one to matter, and its shape is characteristic: the second model does not usually reverse the first, it usually refines it, and the one reversal here is about the one operation whose entire content is moving data around rather than deciding something about it.

There is a fair reading of that which makes the reversal less surprising. A model whose only charge is for moving data will price a pure data-movement problem highest, and a model whose only charge is for touching elements will price it lowest, and neither is a discovery about permutations. What makes the row worth having is that it is checkable: both numbers can be measured on the same run, the ratio between them is 15 at one set of parameters and 0.96 at another, and the parameters at which it turns are computable to the element.

What the plate does not show, and one of it matters #

Three qualifications, and the first is the one that would change a decision.

Reads issued at once. Every read the naive method makes is independent: the addresses are all known before any of them is issued, so a device accepting a hundred requests at a time can have a hundred of these in flight. The sort’s merge reads are also independent, so both benefit — but the naive method benefits more, because it is nothing but independent reads, and the ratio measured above is a ratio of counts rather than of durations. The block that is not a block sets out why this field refuses to convert one into the other, and this is a case where the refusal is doing real work: the fifteenfold count difference is not a fifteenfold time difference on any device with a deep queue.

Writes are charged and reads are not, symmetrically. Both methods here write as much as they read, so the read-write asymmetry that dominated the previous rung does not separate them. That is a property of this pair rather than of the model.

The elements are one unit each. Every count on this page treats an element as an indivisible thing of a fixed size, which is what makes “$B$ elements to a block” meaningful. A permutation of large records and a permutation of pointers into those records are different problems with different answers — the second moves eight bytes where the first moves hundreds, and the indirection it buys costs a scattered read on every later access. Nothing here prices that, and what O notation does not say is the general form of the complaint.

And the permutation is random. A permutation with structure — a transpose, a shuffle by a fixed stride, a rotation — has locality the measurement above deliberately excludes, and each of those has a cheaper specialised method. The bound is a worst case over permutations and the measurement is an average over random ones, and the two agree here only because a random permutation is close to the worst case for this problem.

Where this ladder goes next: the permutation nobody chose #

Two things this rung leaves open, and the second is the larger.

The structured permutations are unmeasured. A matrix transpose is a permutation, it is the single most common one in numerical work, and it has a specialised block algorithm that beats both methods here by tiling. The interesting question is not that the tiled method is faster — it obviously is — but where on the naive-to-sorting axis it sits, and whether the axis has room for it at all. A measurement of transpose against the two methods above, at a range of block sizes, would say whether structure buys a constant or a class.

And the output-sensitivity question is open. The bound above is a worst case over permutations, and a permutation that moves only $k$ elements away from their starting positions should cost something in $k$ rather than in $n$. Nothing in this field has an instrument for that: every measurement here is over a uniformly random $\pi$, and the natural parameter — how far the permutation is from the identity, measured in blocks rather than in inversions — has not been defined, let alone swept. Defining it is the work, and the definition is the interesting part: two permutations with the same number of inversions can have wildly different block behaviour, so the parameter this model wants is not the one the comparison model already has a name for.