Heap Sort
Turn the array into a max-heap, then repeatedly swap the root (maximum) to the end and shrink the heap. O(n log n) worst case with O(1) extra space.
- Category
- Sorting
- Time complexity
- O(n log n)
- Space complexity
- O(1)
Pseudocode
heapSort(A) build max-heap (sift down) root is max swap root/last, shrink, sift done
Reference implementation
# build max-heap, then
for end in range(n-1, 0, -1):
a[0], a[end] = a[end], a[0]
sift_down(a, 0, end)