Course contentsShow
← Computer Science
Lesson 780 of 2,87218. Sorting AlgorithmsFree lesson

In-Place Sorting with Heapsort

How heapsort sorts within the original array without requiring additional space for a separate heap.

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:

  1. Unsorted heap region (at the front)
  2. 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.