Heap Sort: Theory, Implementation, and Step‑by‑Step Explanation

Heap sort is a comparison‑based sorting algorithm that uses a binary heap data structure to sort an array efficiently.

A heap is a complete binary tree where each node satisfies the heap property: in a max‑heap each node is greater than or equal to its children, while in a min‑heap it is less than or equal to them.

The algorithm first builds a max‑heap from the input array, then repeatedly swaps the root (the largest element) with the last element of the unsorted portion and restores the heap property on the reduced heap, producing a sorted sequence.

The article provides a step‑by‑step explanation of heap sort, including why the initial heap construction starts from index ⌊n/2⌋‑1 and proceeds upward, and illustrates the process with an example array int[] arr = {13, 14, 99, 33, 82, 25, 59, 94} .

Two Java code listings are included: the sort method that prints the array state, builds the initial heap, and performs the sorting loop, and the heapAdjust helper that restores the heap property for a given subtree, both annotated with explanatory print statements.

Key points highlighted are the initialization of the max‑heap, the repeated swapping of the heap root with the last unsorted element, and the re‑heapification steps, which together give heap sort its O(n log n) time complexity and in‑place memory usage.

The article concludes that heap sort leverages the memory of the binary heap structure to achieve efficient sorting, and provides references for further reading.