def heap_sort(arr):
n = len(arr)
# build a max-heap in place
for i in range(n // 2 - 1, -1, -1):
sift_down(arr, i, n)
# swap max to the end and re-heapify the prefix
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, i, end):
while True:
j = 2 * i + 1
if j >= end:
return
if j + 1 < end and arr[j + 1] > arr[j]:
j += 1
if arr[i] >= arr[j]:
return
arr[i], arr[j] = arr[j], arr[i]
i = jVariables
n- length of the input array
Explanation
Building the heap is **O(n)** (sift-down work concentrates near the leaves where height is small). Then `n` extract-max operations each cost O(log n) - total **O(n log n)** time. The heap lives in the input array, so only a few index variables are needed for working state - **O(1)** space. Same time class as merge sort, but constant extra memory.