In place is a claim, and it is usually wrong about quicksort

“Quicksort sorts in place; merge sort does not.” It is one of the first things anybody learns about the pair, it is the reason quicksort is the default in most standard libraries, and it is the kind of statement that sounds like a fact about the algorithm rather than a claim about a quantity.

Once the quantity is counted, it is a claim, and it fails.

Peak auxiliary space at $n = 4{,}096$ — the most slots held at any one moment, counting scratch arrays and stack frames together:

Three of those rows are $\Theta(1)$. Three are $\Theta(\log n)$. One is $\Theta(n)$ and is in the same column as merge sort, and it is the algorithm the phrase “in place” is most often used about.

Where the space goes #

Quicksort allocates nothing. There is no buffer, no scratch array, no temporary copy; the partition swaps elements within the input and that is the whole of it. By any accounting that watches the array, it uses no extra memory at all.

It recurses. Each level of recursion is a stack frame holding the bounds of a subproblem, and those frames are live simultaneously — the outer call cannot return until the inner ones have. So the auxiliary space is the depth of the recursion, which is the height of the partition tree.

On random input the partitions are roughly balanced, the tree has depth about $\log_2 n$, and 22 frames at $n = 4{,}096$ is a little above $\log_2 4096 = 12$ because the balance is only roughly right. That is genuinely small and calling it negligible is fair.

On sorted input with a first-element pivot, every partition puts one element on one side and $n-1$ on the other. The tree is a path, its depth is $n$, and the measurement is 4,097 frames for 4,096 elements.

The extra memory has not appeared from nowhere and it is not an artefact of the instrument. It is the call stack, it is proportional to the input, and the reason nobody counts it is that no counter watching the array can see it.

The two failures are the same failure #

Everybody knows first-element quicksort is quadratic on sorted input. It is 8,386,560 comparisons at $n = 4{,}096$, against 57,431 on random input — a factor of 146, and it is the textbook trap.

The space failure is the same event, described in the other resource. An unbalanced partition tree is simultaneously the reason the comparison count is $n^2/2$ and the reason the depth is $n$: one is the number of nodes in the tree and the other is its height.

So the two are not independent risks to weigh separately. They arrive together, they have one cause, and every fix for one is a fix for the other. What differs is the failure mode, and this is the part worth having:

The time failure degrades. A quadratic sort of 4,096 elements takes longer. It finishes. Somebody notices a slow request.

The space failure stops. A recursion 4,096 deep is fine; one seven thousand deep, on the machine this site is built on, is not. The program does not slow down — it raises a stack-overflow error and dies, at a size that depends on the engine, on the frame layout and on how much stack the caller had already used.

One of those is a performance problem and one is an availability problem, and the space axis is the only one that shows the second exists.

The real stack, and why the figure does not use it #

The interesting version of this is not the modelled stack in that figure but the actual one, and it is worth reporting exactly because it is the reason the figure uses a model instead.

Running first-element quicksort on a sorted array on the machine that builds this site: it succeeds at $n = 7{,}000$ and fails at $n = 7{,}015$ with a stack-overflow error. Bisecting for the precise threshold is possible, and the precise threshold is not reproducible — running the same size again after other work has been done gives a different answer, because the available stack depends on how much of it the caller has already spent.

That is a real measurement of a real failure and it cannot go in a caption. A number that changes between builds is a number the reader’s copy of the page does not have, which is the same reason no figure here uses Math.random().

So the figures use a stated stack — a limit in frames, printed on the figure, exactly as the cache model prints its line size. The gate then requires the modelled stack to bite: with 256 frames and 2,048 sorted elements, the first-element pivot must fail and median-of-three must not. A limit that rejects everything proves as little as one that rejects nothing, so both halves are checked.

A space claim the fit refused #

Every algorithm here declares a space class per input, and the classes are put through the same ratio test the comparison counts get. Most of them pass comfortably — heapsort’s peak ÷ 1 has a spread of 1.00 across $n$ from 128 to 32,768, merge sort’s peak ÷ $n$ has a spread of 1.07.

Median-of-three quicksort declared $\Theta(\log n)$ on nearly-sorted input. The fit refused it, and the measurement is worth showing:

Logarithmic up to eight thousand, and then it is not. The spread of peak ÷ $\log n$ across the whole range is 7.17 and the class is not granted; the claim was removed from the table rather than kept with a caveat.

What causes the jump is the interaction between the pivot rule and the input generator. Nearly-sorted input here is a sorted array with $n/20$ adjacent transpositions, so the median of the first, middle and last elements is almost always an excellent pivot — until a subproblem happens to be short enough and disturbed enough that all three samples come from the same end of it, at which point that branch descends much further than the others. The depth is the maximum over branches, so one bad branch sets the number, and the probability of at least one bad branch grows with the number of branches.

This is the third declared class this site has withdrawn on measurement, after bubble sort on nearly sorted input and the hybrid on reversed input, and it is the first one in the space column. The pattern in all three is identical: the class is right about the average or about the asymptotics, the measurement is of the maximum over a finite range, and the two are different quantities.

The in-place merge sorts, and what they cost #

If merge sort’s only defect is its buffer, the obvious question is whether the buffer can be removed. It can, and the answer is instructive because it is a trade rather than a fix.

Rotation-based in-place merge. Merge two adjacent sorted runs by repeatedly rotating blocks into place rather than copying into scratch. Auxiliary space becomes $O(1)$; the comparison count is unchanged; the data movement rises from $\Theta(n \log n)$ to $\Theta(n \log^2 n)$, because a rotation moves elements that a copy would have left alone. The algorithm has bought the space axis by giving up on the traffic axis, which is the count that usually decides when elements are anything larger than an integer.

Block merge, or “grail” sorting. Steal a block of $\sqrt n$ elements from the array itself to use as scratch, merge in blocks, then sort the stolen block back into place. Auxiliary space is $O(1)$ genuinely, the movement stays $\Theta(n\log n)$, and the constant is several times plain merge sort’s. It is the sophisticated answer and it is a few hundred lines where merge sort is twenty.

A rotating buffer of $\sqrt n$. The intermediate point: $\Theta(\sqrt n)$ auxiliary space, movement close to the plain algorithm’s. At $n = 4{,}096$ that is 64 slots rather than 4,096 — a factor of 64 saved for a modest constant.

Set those beside the algorithms already measured and the picture is a curve rather than two options:

Two of those rows are measured here — plain merge sort at 4,110 and heapsort at 1 — and the rest are arithmetic from the published designs, since this site implements neither the block merge nor the rotation merge. They are in the table because the shape is the point and the shape does not depend on the exact constants.

Nothing on that list is free, and the two that reach one slot pay in the two different currencies the site measures. Which is the whole argument of the space field compressed into a table: auxiliary space is a resource that trades against the others, so the algorithms that need none of it are paying for that somewhere, and the payment is measurable.

It is also why the phrase is doing damage rather than merely being imprecise. Calling quicksort in-place and merge sort not in-place collapses that table into two categories, puts quicksort in the wrong one, and hides the intermediate options entirely.

What “in place” ought to mean #

Three definitions are in circulation and they disagree about quicksort, which is why the phrase is doing so little work.

$O(1)$ auxiliary space. The strict reading. Heapsort qualifies, Shellsort qualifies, insertion and selection and bubble sort qualify. Quicksort does not, on any input, because $\log n$ is not $O(1)$.

$O(\log n)$ auxiliary space. The reading that lets quicksort in, and the one most textbooks are implicitly using. It is defensible — 22 slots for 4,096 elements is not a memory problem — and it has a hole in it, which is that quicksort’s $O(\log n)$ is an average-case statement and the phrase is used as though it were a guarantee.

No allocation. The reading a systems programmer often means: the algorithm calls no allocator, so it cannot fail on memory pressure and cannot fragment the heap. Quicksort qualifies and merge sort does not, and this reading is genuinely useful and genuinely different from the other two — and it says nothing at all about the stack, which is where quicksort’s failure lives.

None of the three is wrong. The problem is that they are three, they select different sets of algorithms, and the phrase is used as though there were one. A number does not have that problem: quicksort’s peak is 22 on random input, 4,097 on sorted input with the wrong pivot rule, and 14 with a good one.

What a language does not do about it #

The smaller-side fix is described below as a two-line change with no cost, and it is worth noticing what happens without it in a language that eliminates tail calls — because the answer is nothing, and the reason is instructive.

Quicksort’s second recursive call is in tail position: nothing happens after it returns. So a runtime with proper tail calls does not allocate a frame for it, and the recursion depth becomes the length of the chain of first calls rather than the depth of the whole tree.

That does not fix anything on its own. If the first call is on the larger side, the chain of first calls can be $n$ long, and the depth is $n$ with or without tail-call elimination. Tail calls remove the frames of the branch that was already going to be shallow if the order were right, and leave the deep branch exactly where it was.

So the two changes have to be made together, and the one that matters is the ordering rather than the language feature. Recursing on the smaller side first bounds the first-call chain at $\log_2 n$ by itself, whether or not the second call costs a frame; tail-call elimination then removes the remaining frames and makes the space genuinely constant rather than logarithmic.

That is worth carrying past quicksort, because the pattern covers every algorithm that divides into two parts and handles them in sequence. Quickselect, a binary-tree traversal, the divide step of a linear-space alignment, a range query over an interval tree: in each case the depth is set by which part is descended into first, the smaller-first rule bounds it at a logarithm on every input, and the rule costs a comparison. The stack nobody counts is where the resource is measured; this is the one-line fix that applies to all of them.

The phrase also hides stability #

There is a second property the two words collapse, and it is the one that decides which sort a library uses for objects.

A stable sort keeps equal elements in their original relative order, which is what makes sorting by one key and then another produce a sensible result. Merge sort is stable. Heapsort is not, quicksort is not, Shellsort is not — and those are precisely the algorithms at the low-space end of the table.

That is not a coincidence and it is close to a theorem in practice: the known comparison sorts that are simultaneously stable and $O(1)$ in auxiliary space are the block-merge constructions in the list above, and they are several hundred lines with large constants. Everything simple is stable or frugal with space, not both.

So “sorts in place” is being used to make a decision that has three axes in it — space, stability, and how much code somebody is prepared to maintain — and it names one of the three. A library that has to sort objects picks the stable algorithm and pays the buffer, which is exactly what Java does and exactly what C++'s two separate entry points make explicit; a library sorting integers picks the frugal one because stability is meaningless when equal elements are indistinguishable.

The phrase’s real failure is not that it is imprecise about quicksort’s space. It is that it presents a three-way engineering decision as a binary property of algorithms, and the property it names is the one it gets wrong.

What a library actually promises #

Standard libraries are more careful about this than textbooks are, and reading what they promise is instructive.

C++'s std::sort guarantees $O(n\log n)$ comparisons and says nothing about space, and its typical implementation is an introsort whose recursion is bounded at $2\log_2 n$. C++'s std::stable_sort explicitly promises to try for a buffer of $n$ and to degrade to $O(n\log^2 n)$ comparisons if it cannot get one — a published, documented trade between the two axes, stated as such.

Both of those are more precise than “sorts in place”, and neither uses the phrase. The vocabulary problem this essay is about is a teaching problem rather than an engineering one: the people who had to write the guarantee down found that the phrase would not do the job.

The measurement is a peak over one run, so it is worth taking on three inputs and two sizes before any of it is quoted.

The input is the second dial, and it is the one that separates a peak fixed by the algorithm from a peak the data chooses.

One more input, because sorted and reversed are the two ends a naive pivot rule is worst on and they are not the same end.

What to do about it, and what it costs #

The fixes are all well known and it is worth putting the space cost of each beside the time cost, because they are not the same list.

Randomise the pivot. Removes the input’s ability to choose the bad case, in both resources at once: peak 28 on random input and 32 on sorted input, which is what randomisation buys showing up in the space column. Costs a random number per partition.

Recurse on the smaller side, loop on the larger. This is the one that actually bounds the space, and it is a two-line change with no cost at all. Since the smaller side has at most $n/2$ elements, the recursion depth is at most $\log_2 n$ on every input, including the pathological ones. The comparison count is unchanged — the algorithm does exactly the same work in the same order — and the $\Theta(n)$ row in the first table becomes $\Theta(\log n)$.

That it is free, well known, and absent from most presentations of the algorithm is the strongest argument in this essay. A worst case that costs nothing to remove is a worst case people would remove if they knew it was there, and the reason they do not know is that the resource it lives in is not the one anybody counts.

Switch to heapsort when the recursion gets deep. Introsort’s answer: bound the depth at $2\log_2 n$ and fall back to an algorithm with a worst-case guarantee in both resources. This is what most standard libraries do and it is a decision about the space axis at least as much as the time one.