Heap Sort
Heap sort is a comparison-based sorting algorithm that uses a binary heap data structure to sort elements in place. It works in two phases: first building a max-heap from the input array, then repeatedly extracting the maximum element from the heap and placing it at the end of the sorted portion. Heap sort guarantees O(n log n) time complexity in all cases and O(1) auxiliary space, making it optimal for scenarios where both time efficiency and memory constraints matter.
Key Formula
T(n) = O(n log n)
LaTeX: T(n) = O(n \log n)
| Symbol | Meaning | Unit |
|---|---|---|
| T(n) | Total sorting time | operations |
| n | Number of elements to sort | elements |
| log n | Height of the binary heap | levels |
Worked Example
Problem
Sort the array [4, 10, 3, 5, 1] using heap sort.
Solution
Phase 1 – Build max-heap: Starting from last non-leaf (index 1): heapify [4, 10, 3, 5, 1] → max-heap: [10, 5, 3, 4, 1]. Phase 2 – Extract max: Swap root 10 with last element 1 → [1, 5, 3, 4 | 10]. Heapify [1,5,3,4] → [5,4,3,1]. Swap 5 with 1 → [1,4,3 | 5,10]. Heapify → [4,1,3]. Swap 4 with 3 → [3,1 | 4,5,10]. Heapify → [3,1]. Swap 3 with 1 → [1 | 3,4,5,10]. Final array: [1,3,4,5,10].
Answer
Sorted array: [1, 3, 4, 5, 10].
Heap Sort Complexity and Properties
| Property | Value | Notes |
|---|---|---|
| Best Case Time | O(n log n) | Always performs heapify operations |
| Average Case Time | O(n log n) | Consistent regardless of input |
| Worst Case Time | O(n log n) | Guaranteed upper bound |
| Space Complexity | O(1) | In-place, no extra array |
| Stability | Unstable | Long-distance swaps disrupt order |
| Build Heap Phase | O(n) | Linear time heap construction |
Interactive Tools
Wikimedia Commons, CC BY-SA
Related Terms
Merge Sort
Merge sort is an efficient, stable, divide-and-conquer sorting algorithm that works by recursively splitting an array into two halves, sorting each half, and then merging the sorted halves back together. It guarantees a time complexity of O(n log n) in all cases — best, average, and worst — making it more predictable than quicksort. Merge sort is the preferred algorithm for sorting linked lists and is used in many standard library implementations such as Python's Timsort.
Quick Sort
Quick sort is a highly efficient, in-place divide-and-conquer sorting algorithm that selects a "pivot" element and partitions the array into two sub-arrays — elements less than the pivot and elements greater than the pivot — then recursively sorts each sub-array. It achieves an average time complexity of O(n log n) and is often faster in practice than merge sort due to better cache performance and lower constant factors. Quick sort is widely used in standard library implementations, including the C++ STL and Java's Arrays.sort for primitive types.
Time Complexity
Time complexity is a measure of the amount of time an algorithm takes to complete as a function of the size of its input, typically expressed using Big O notation. It describes how the running time grows relative to the input size, helping developers predict performance and compare algorithms. Understanding time complexity is essential for writing scalable software, especially when dealing with large datasets.
Heap sort was invented by J.W.J. Williams in 1964, who also introduced the binary heap data structure in the same paper. Robert Floyd subsequently improved the algorithm with an efficient heap-building procedure in 1964, which reduces the build-heap phase to O(n) time.