Heapsort is a comparison sort that uses a binary heap to repeatedly extract the maximum. It runs in O(n log n) time, in place, with O(1) extra space — the only mainstream comparison sort with all three properties.
| Best | Average | Worst | Space (Worst) |
|---|---|---|---|
Ω(n log n) |
Θ(n log n) |
O(n log n) |
O(1) |
First, heapify the array into a max-heap in O(n). Then repeatedly: swap the root (largest element) with the last element of the heap, shrink the heap by one, and sift the new root down. After n iterations the array is sorted ascending.
def heapsort(arr):
"""In-place heapsort using a max-heap."""
n = len(arr)
def sift_down(start, end):
root = start
while 2 * root + 1 < end:
child = 2 * root + 1
if child + 1 < end and arr[child] < arr[child + 1]:
child += 1
if arr[root] < arr[child]:
arr[root], arr[child] = arr[child], arr[root]
root = child
else:
return
for start in range(n // 2 - 1, -1, -1):
sift_down(start, n)
for end in range(n - 1, 0, -1):
arr[0], arr[end] = arr[end], arr[0]
sift_down(0, end)
return arr
print(heapsort([3, 6, 1, 8, 2, 9, 4])) # [1, 2, 3, 4, 6, 8, 9]