In-Place Sorting with Heapsort
What you'll learn: How heapsort achieves efficient sorting without using extra memory by cleverly reusing the original array.
The Space-Saving Magic
You've already learned how heapsort converts an array into a max-heap and repeatedly extracts the maximum element. But here's the beautiful trick: heapsort doesn't need a separate array to hold the sorted elements. It sorts in-place within the original array itself.
How It Works
Think of the array as having two logical regions:
- Unsorted heap region (at the front)
- Sorted region (at the back)
Initially, the entire array is the heap. After each extraction:
- The max element (at index 0) gets swapped with the last element in the heap region
- That max element now sits at the beginning of the sorted region
- The heap shrinks by one element
- The sorted region grows by one element
For example, with array [50, 40, 30, 20, 10] (already a max-heap):
- Swap 50 and 10 →
[10, 40, 30, 20 | 50] - Heapify the smaller heap on the left
- Repeat until the heap region disappears
The Memory Advantage
Because the sorted elements accumulate at the end of the array while the heap shrinks from the beginning, they never interfere with each other. The sorted portion grows exactly as the heap portion shrinks, using the same memory locations.
This means heapsort uses only O(1) extra space—just a few variables for tracking indices and temporary swaps. No auxiliary arrays needed!
Key Takeaway: Heapsort sorts in-place by partitioning the array into shrinking heap and growing sorted regions, achieving O(n log n) time with O(1) space complexity.