In-Place vs Out-of-Place Sorting

Every sorting algorithm needs the array itself, so "space complexity" always means auxiliary space — the scratch memory needed on top of the input. Strictly, in-place means O(1) auxiliary space: a handful of loop counters and temporaries, whatever the input size.

The part that trips people up is recursion. Quick Sort allocates no arrays, but each recursive call consumes a stack frame, and with balanced partitions the recursion is O(log n) deep. So Quick Sort's auxiliary space is O(log n), not O(1).

By convention it is still called in-place, because O(log n) is negligible: for a billion elements, log₂n is only about 30 frames. In interviews, say "in-place, with O(log n) stack space for the recursion" — it is precise, and it signals that you thought about the stack rather than only about arrays.

One more wrinkle worth knowing: the stack depth depends on the partitioning. If you always recurse into the smaller partition first and loop on the larger one (tail-call elimination), the depth is bounded at O(log n) even in the worst case. Without that, a degenerate Quick Sort can recurse O(n) deep and overflow the stack — which is a crash, not just a slowdown.

In-place, O(1) auxiliary space:

• Bubble Sort — swaps adjacent pairs, needs one temporary.
• Selection Sort — tracks a minimum index and swaps.
• Insertion Sort — shifts elements right and drops one value back in.
• Shell Sort — gapped insertion sort; still just shifting.
• Heap Sort — builds the heap inside the array itself, iteratively.

In-place by convention, O(log n) stack:

• Quick Sort — partitions in place, recursion costs stack frames.
• Introsort — Quick Sort plus Heap Sort, so the same bound.

Out-of-place:

• Merge Sort — O(n) buffer for merging.
• Tim Sort — O(n) worst case for its merges (often less in practice).
• Counting Sort — O(k) tally array plus O(n) output.
• Radix Sort — O(n + k), using Counting Sort per digit.
• Bucket Sort — O(n + k) for the buckets.

A pattern worth noticing: Heap Sort is the only algorithm in the top group that is also O(n log n) in the worst case. That combination — guaranteed time and constant space — is exactly why it survives despite being slower than Quick Sort in practice.

Extra memory is not wasted; it buys specific properties.

Out-of-place buys stability. Merging two runs into a buffer makes preserving the order of equal elements trivial: when values tie, always take from the left run. Doing the same in place requires moving elements over long distances, and long-distance moves are what destroy relative order. This is why almost every stable algorithm either uses a buffer (Merge, Tim, Counting, Radix) or only ever shifts by one position (Insertion, Bubble), and why every unstable one (Quick, Heap, Selection, Shell) does long-distance swaps.

Out-of-place buys simpler correctness. Merge Sort's guarantee of O(n log n) in all cases is easier to achieve when you are not fighting for space. In-place merge algorithms exist, but they are intricate and slower by a large constant — enough that nobody uses them in practice.

In-place buys cache locality and allocation-free operation. One region of memory means less cache pressure, which is a large part of why Quick Sort outruns Merge Sort in RAM. It also means no allocation, which matters when allocation can fail or stall.

So the choice is roughly: constant memory and raw speed, or stability and predictability. You do not usually get both. The exception is Heap Sort, which gives you constant memory and a worst-case guarantee — and pays for it by being unstable and cache-hostile.

Most of the time you can ignore it. These are the cases where you cannot.

Sorting a large fraction of available memory. If a dataset occupies 60% of your RAM, an O(n) auxiliary buffer needs another 60% and the sort fails or starts swapping. Heap Sort will finish. Beyond that, the answer is external sorting.

Embedded and real-time systems. A microcontroller with a few kilobytes of RAM cannot allocate a second array, and many real-time systems forbid dynamic allocation entirely because it makes timing unpredictable. Heap Sort and Shell Sort are common here — Shell Sort especially, because it is also non-recursive, so it needs no meaningful stack either.

Deep recursion risk. On a thread with a small stack, an unguarded Quick Sort on adversarial input can recurse O(n) deep and overflow. This is a crash rather than a slow query, which makes it worse than the O(n²) time it is usually discussed alongside. Recursing into the smaller side first fixes it.

Kernel and allocator code. Code that runs below the allocator cannot call it, so in-place is not a preference but a requirement.

Linked lists invert the usual answer. Merge Sort on a linked list needs no buffer at all — merging is pointer rewiring — so it is O(1) auxiliary space there, while Quick Sort loses the random access it depends on. The algorithm labelled "out-of-place" becomes the in-place one, purely because the data structure changed.

A few phrasings that hold up under follow-up questions.

Say auxiliary space rather than "space", because it makes clear you are not counting the input. Say "in-place with O(log n) stack space" for Quick Sort rather than claiming O(1). Note that Heap Sort is the only common algorithm with both O(n log n) worst case and O(1) space — it is the answer to "when would you use Heap Sort at all?". And mention that Tim Sort's O(n) figure is a worst case; its merges frequently need far less, which is part of why it is acceptable as a default despite being out-of-place.

If any of this feels abstract, the visualiser makes it visible: watch Insertion Sort and you will see values shift one slot at a time within the single row of bars, and watch Merge Sort and you will see whole blocks rewritten at once — that rewriting is the buffer doing its work.