Loading...
Heap Sort turns the array into a binary max-heap, then repeatedly swaps the root (the maximum) to the end and restores the heap over the shrinking prefix. It sorts in place with a guaranteed O(n log n) worst case, though it is not stable and has worse cache behavior than Quick Sort.
Builds a max-heap, then repeatedly extracts the maximum.
| Best case | O(n log n) |
| Average case | O(n log n) |
| Worst case | O(n log n) |
| Space | O(1) |
| Stable | No |
Complexities are for the reference implementation shown; constant factors and cache behavior vary by language.
Idiomatic, copy-paste implementations. Pick your language:
Python
def heap_sort(arr):
n = len(arr)
for i in range(n // 2 - 1, -1, -1):
sift_down(arr, i, n)
for end in range(n - 1, 0, -1):
arr[0], arr[end] = arr[end], arr[0]
sift_down(arr, 0, end)
return arr
def sift_down(arr, root, size):
while True:
largest, l, r = root, 2 * root + 1, 2 * root + 2
if l < size and arr[l] > arr[largest]: largest = l
if r < size and arr[r] > arr[largest]: largest = r
if largest == root: return
arr[root], arr[largest] = arr[largest], arr[root]
root = largestSorting [5, 1, 4, 2] step by step:
The control flow of the algorithm as a diagram: