# Heapsort - $O(n\lg n)$, but sorts **in place**, so that the memory usage is constant. - Utilizes the [[heap]] data structure. ```python heapsort(A, n) for i = n downto 2 exchange(A[1], A[i]) A.heap_size -= 1 max_heapify(A, 1) ```