What Is In-Place Sorting?
The term in-place sorting appears in almost every algorithm comparison, but its meaning is often glossed over. An in-place algorithm sorts the data using only a constant amount of extra memory — it rearranges elements within the original array rather than building a copy.
The definition
An algorithm is in-place if its auxiliary space is O(1) — a fixed number of temporary variables regardless of input size. Note that recursion stack space is sometimes overlooked: Quick Sort is generally called in-place even though it uses O(log n) stack space, because it does not allocate a second array.
Which algorithms are in-place
In-place: Bubble, Selection, Insertion, Quick, Heap, and Shell Sort. Not in-place: Merge Sort (needs an O(n) merge buffer), Counting Sort (needs O(k) counts), Radix Sort, and Tim Sort. This is why Heap Sort is prized — it is the only comparison sort that is both O(n log n) and in-place.
The trade-off
In-place sorting saves memory but can cost stability or simplicity. Merge Sort gives up in-place operation to gain stability and guaranteed O(n log n). When memory is tight, choose an in-place sort; when stability is required, you usually accept the extra O(n) space. Explore both kinds in the visualizer to feel the difference.
Frequently asked questions
Is Quick Sort in-place? +
Why is Merge Sort not in-place? +
See it in motion
Watch this algorithm and 9 others run step by step in our free interactive visualizer.
▶ Launch Visualiser