Space Complexity in Sorting Algorithms
Speed gets all the attention, but memory matters too — especially on embedded devices or when sorting huge datasets. Space complexity measures the extra memory an algorithm needs beyond the input array itself. This article explains the spectrum from O(1) in-place sorts to O(n) auxiliary-space sorts.
Auxiliary space vs total space
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).
The memory ranking
- 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.
When memory is the deciding factor
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.
Frequently asked questions
Which sorting algorithm uses the least memory? +
Why does Merge Sort need O(n) space? +
See it in motion
Watch this algorithm and 9 others run step by step in our free interactive visualizer.
▶ Launch Visualiser