Sort an Array

Sort an Array is the problem where the catch is in the rules: you must sort the numbers without using the language's built-in sort, in O(n log n) time and ideally without much extra space. That points straight at heap sort — an in-place O(n log n) sort built on the binary-heap idea.

The slow way first

The obvious idea is one of the quadratic sorts — selection or bubble sort: repeatedly scan the array to find the next value to place. That works, but each scan is O(n) and we do n of them, so it is O(n²) — too slow for the required bound.

The question to ask: how do I find the maximum remaining value over and over without rescanning the whole array each time? A heap answers exactly that. A max-heap always keeps its largest value at the root, and re-balancing after we remove it costs only O(log n), not O(n).

The idea: heapify, then extract

Treat the array as a complete binary tree, where index i has children at 2i+1 and 2i+2. Heap sort runs in two phases:

1. Build a max-heap. Sift down every parent, starting from the last parent at index n//2 - 1 back to the root. After this pass the largest value sits at index 0.
2. Extract repeatedly. Swap the root (the max) with the last cell, shrink the heap by one, and sift the new root back down. Each swap locks one more value into its final sorted position, growing the sorted region from the right.

The key insight: sift-down is the only primitive we need. A node out of heap order trades places with its larger child and keeps sinking until both children are smaller. Building the heap is O(n); each of the n extractions costs O(log n), so the whole sort is O(n log n).

Walk through it

Step through the animation. The node pointer marks the index being sifted and child marks its larger child. First the build phase reshapes [5, 3, 6, 1, 4] into a max-heap (6 rises to the root). Then each extraction swaps the root to the end — watch the sorted cells fill in from the right until the whole array is ordered.

Pseudocode

heapify(a, n, i):                 # sift index i down within a heap of size n
    largest = i
    if left child  > a[largest]:  largest = left
    if right child > a[largest]:  largest = right
    if largest != i:
        swap a[i] and a[largest]
        heapify(a, n, largest)    # keep sinking
 
sort:
    for i from n//2 - 1 down to 0:    # phase 1: build the max-heap
        heapify(a, n, i)
    for end from n-1 down to 1:       # phase 2: extract the max
        swap a[0] and a[end]
        heapify(a, end, 0)            # re-sift the smaller heap

The Python solution

def heapify(a, n, i):
    largest = i
    l, r = 2 * i + 1, 2 * i + 2
    if l < n and a[l] > a[largest]:
        largest = l
    if r < n and a[r] > a[largest]:
        largest = r
    if largest != i:
        a[i], a[largest] = a[largest], a[i]
        heapify(a, n, largest)
 
def sort_array(a):
    n = len(a)
    for i in range(n // 2 - 1, -1, -1):
        heapify(a, n, i)
    for end in range(n - 1, 0, -1):
        a[0], a[end] = a[end], a[0]
        heapify(a, end, 0)
    return a

• heapify(a, n, i) sifts index i down within the first n cells: it finds the larger of i and its two children, and if a child wins, it swaps and recurses from that child.
• l, r = 2 * i + 1, 2 * i + 2 are the indices of the left and right children in the array layout of the tree.
• The build loop runs heapify on every parent from n//2 - 1 back to 0; leaves (the last half) are already trivial heaps, so we skip them.
• The extract loop swaps the root with index end, locking the max into place, then calls heapify(a, end, 0) — note the heap size is now end, so the just-placed cell is excluded.
• The whole thing is in place: no second array, only swaps and the recursion stack.

Complexity

Heap sort hits the required O(n log n) bound in every case and uses only O(1) extra space (ignoring the recursion stack, which is O(log n) and can be made iterative). That is its selling point versus quicksort, whose worst case is O(n²), and merge sort, which needs O(n) extra space.

When this pattern shows up

Practice