Heapsort Space Complexity and Stability
You'll learn why heapsort is space-efficient but doesn't preserve the original order of equal elements.
Space Complexity: O(1) Extra Space
Heapsort operates in-place, meaning it sorts the array without requiring additional arrays or data structures proportional to the input size. The array itself is rearranged to form a heap, and the sorting happens by swapping elements within that same array.
Why O(1)? You only need a constant amount of extra memory for variables like loop counters and temporary swap storage. No matter how large your input array grows, the extra space remains fixed.
Analogy: Imagine sorting books on a shelf by rearranging them directly on that shelf, rather than moving them to a second shelf. You might hold one book temporarily in your hands (constant space), but you don't need a whole second shelf.
Stability: Heapsort is NOT Stable
A sorting algorithm is stable if it preserves the relative order of equal elements. For example, if two items have the same priority but appeared in a specific order originally, a stable sort keeps that order.
Why heapsort is unstable: During the heapify-down operations and extract-max phase, elements are moved based solely on their values, not their original positions. Equal elements can leapfrog each other during these swaps, breaking their original order.
Example: Sorting [(5, "first"), (3, "x"), (5, "second")] by the number might produce [(3, "x"), (5, "second"), (5, "first")] — notice the two 5s swapped positions.
If you need stability, consider merge sort or insertion sort instead.
Key Takeaway: Heapsort achieves O(1) extra space complexity by sorting in-place, but it is not a stable sorting algorithm because heap operations can rearrange equal elements unpredictably.