Heapsort Space Complexity
What you'll learn: You'll understand why heapsort uses only O(1) extra space and what makes it truly in-place.
When we talk about a sorting algorithm's space complexity, we're asking: "How much extra memory does this need beyond the input array itself?"
Heapsort shines here because it operates in-place, meaning it rearranges elements within the original array without needing a separate storage structure. Unlike mergesort, which requires O(n) auxiliary space for temporary arrays during the merge process, heapsort transforms the input array into a heap structure and then sorts it—all using the same memory locations.
Why O(1) Auxiliary Space?
The magic happens because:
- The heap is built directly in the array – no separate heap data structure is allocated
- Sorting happens by swapping – we repeatedly swap the root (largest element) with the last unsorted position
- Only a few variables are needed – things like loop counters, indices, and temporary swap variables
Think of it like reorganizing books on a single shelf. You don't need a second shelf (extra space); you just keep moving books around on the same shelf until they're in order.
The Fine Print
Technically, heapsort does use O(log n) space for the recursion stack if you implement the heapify operation recursively. However, this can be eliminated with an iterative implementation, achieving true O(1) space. Even with recursion, O(log n) is still considered "in-place" for practical purposes.
Key Takeaway: Heapsort achieves O(1) auxiliary space complexity by sorting directly within the input array, making it a space-efficient alternative to mergesort while maintaining O(n log n) time complexity.