Heap Sort

• Optimization over selection sort
• Not stable sorting
• Used in hybrid sorting algo like Intro Sort
• Time: $θ(n log n)$, Space: $O(1)$
• 2 steps:
  1. Build a MaxHeap
  2. Repeatedly swap root with the last node, reduce heap size by 1 and heapify

Python

def buildHeap(arr):
    N = len(arr)
    for i in range((N - 2) // 2, -1, -1):
        maxHeapify(arr, N, i)

def maxHeapify(arr, n, i):
    largest = i
    left, right = 2 * i + 1, 2 * i + 2
    if left < n and arr[left] > arr[largest]:
        largest = left
    if right < n and arr[right] > arr[largest]:
        largest = right
    if largest != i:
        arr[i], arr[largest] = arr[largest], arr[i]
        maxHeapify(arr, n, largest)

def heapSort(arr):
    buildHeap(arr)
    N = len(arr)
    for i in range(N - 1, 0, -1):
        arr[i], arr[0] = arr[0], arr[i]
        maxHeapify(arr, i, 0)