Skip to main content

Heap Sort

Learn Heap Sort (Sorting, Data Structures & Algorithms) with worked examples, diagrams and interview questions. Free on JavaSchoolLab.

Heap Sort - O(n log n), In-Place, No Worst-Case Surprises Builds a MAX-HEAP from the array, then repeatedly swaps the root (the maximum) with the last unsorted element and "sinks" the new root back down - shrinking the heap by one each time. Guaranteed O(n log n) in every case, no adversarial input can degrade it, unlike Quick Sort. In-place - O(1) extra space, sorts within the same array. Not stable - heap operations can reorder equal elements.

More lessons in Sorting