Unit 4 · Lesson 716 minAcademic review pending

The emergency room, run until it's empty

Unit III's heap always hands you the most extreme value. Heap sort simply asks for it, over and over, writing each answer into the back of the array as it goes.

Choose explanation

After this lesson

You should be able to

Sort an array in place using heap sort.
Explain why heap sort needs no extra array, unlike a merge-based sort.
State heap sort's time complexity and where it comes from.

Extract the max, forever, into the back

Unit III Lesson 6 briefly mentioned this as a heap application. Here is the whole algorithm: build a max-heap from the array, then repeatedly extract the maximum — but instead of throwing it away, swap it into the last unsorted slot of the very same array, shrink the heap's boundary by one, and bubble-down to restore the heap property on what remains.

Because the extracted value is swapped within the same array rather than copied elsewhere, heap sort needs no second array — unlike a merge sort, which needs extra space proportional to the input size. That single property is why heap sort is often chosen when memory is tight.

Build once, then extract-and-shrink n - 1 times

void heap_sort(int arr[], int n)
{
    build_max_heap(arr, n);          /* Unit III Lesson 5's insert logic,
                                         applied to the whole array at once */

    for (int end = n - 1; end > 0; end--) {
        swap(&arr[0], &arr[end]);     /* move the max to its sorted spot */
        bubble_down(arr, 0, end);     /* restore the heap on what remains */
    }
}

Where the cost comes from

Building the initial heap costs roughly n operations. Each of the n - 1 extractions costs at most the heap's height, about log n, for its bubble-down. Multiplying those together gives n log n overall — the same bound as the best comparison-based sorts can achieve, matching the proven limit Lesson 6 mentioned, with no extra memory needed to hit it.

Try it yourself

Trace heap sort on the array [4, 10, 3, 5, 1] by hand: build the max-heap first, then perform each extract-and-shrink step, writing the array after each step.

Need a hint?

Building the heap itself may require a few bubble-down steps before the array even looks like a valid max-heap — do that first, separately from the extraction loop.

Check the worked solution

Building the max-heap from [4, 10, 3, 5, 1] gives [10, 5, 3, 4, 1]. Extracting repeatedly: swap 10 to the end and bubble-down gives [5, 4, 3, 1 | 10]; swap 5 to the end gives [4, 1, 3 | 5, 10]; swap 4 to the end gives [3, 1 | 4, 5, 10]; swap 3 to the end gives [1, 3, 4, 5, 10], now fully sorted. The bar marks the growing sorted region at the back, exactly as the code's shrinking `end` boundary describes.

Quick check

Why does heap sort need no second array, unlike a typical merge sort?

Select an answer to check your thinking.

Why this lesson exists

Syllabus mapping

Heap sort

Maps to course outcomes CO1, CO3.