Space Complexity in Sorting Algorithms

Space complexity for sorting usually refers to auxiliary space — the extra memory used on top of the original array. The array itself is not counted because every algorithm needs it. An algorithm that sorts using only a few extra variables is O(1); one that allocates a second array the size of the input is O(n).

• O(1) — Bubble, Selection, Insertion, Heap Sort. They rearrange elements in place with only a handful of temporary variables.
• O(log n) — Quick Sort, from the recursion call stack.
• O(n) — Merge Sort and Tim Sort, which need a buffer to merge into.
• O(k) — Counting Sort, proportional to the range of values.

If you are sorting on a memory-constrained system, Heap Sort is attractive because it guarantees O(n log n) time with O(1) extra space. When data is too large to fit in RAM entirely, external Merge Sort wins because it streams sequential chunks from disk. The visualizer labels each algorithm's space cost so you can compare at a glance.

An algorithm sorts in place if it needs only a constant amount of extra memory — O(1) auxiliary space — rearranging values inside the original array instead of building a second one. The input array itself does not count towards this; the question is only how much additional space is required.

Here is where each classic algorithm lands:

The trade-off is nearly always memory against one of two other properties. Merge Sort spends O(n) extra space and buys guaranteed O(n log n) time and stability. Heap Sort spends nothing extra and matches the time guarantee, but gives up stability to do it. Quick Sort spends only stack space and is faster in practice, but gives up the worst-case guarantee.

There is no algorithm that is simultaneously in-place, stable, and guaranteed O(n log n) with small constants. Every practical sort picks which of those to sacrifice, and knowing which one it sacrificed is most of what you need to choose between them.