Heapsort

Heapsort is a comparison-based sorting algorithm that sorts an array by transforming it into a binary heap, a nearly complete binary tree that satisfies the heap property. With a max-heap, the largest element is always at the root, which enables efficient extraction of the next largest item.

The standard implementation uses an in-place array representation of a binary heap. For 0-based indexing, the left child of index i is at 2i + 1, the right child at 2i + 2, and the parent at floor((i − 1) / 2). The algorithm consists of two phases. First, build a max-heap from the input array in O(n) time by applying heapify-down to all non-leaf nodes from the middle of the array toward the root. Second, repeatedly swap the root (maximum) with the last unsorted element, reduce the heap size by one, and restore the max-heap property by heapifying down from the root.

Heapsort sorts in O(n log n) time in all cases and operates in-place, using only a constant amount of auxiliary space. It is not a stable sort, meaning equal elements may not retain their relative order. It is also not adaptive, so it does not gain advantage from existing order in the input. To obtain descending order, one can use a min-heap or invert the comparison when building the heap.

Because of its in-place memory usage and guaranteed worst-case time complexity, heapsort is often used in systems where memory is constrained or a simple, non-recursive sorting algorithm is preferred.