The Complete Sort

With the two changes, sink works on a max-heap and stops at a given size. Now we put the sort together.

buildHeap is unchanged

buildHeap runs the same loop. Its sink calls now pass a size, and while building, the heap is the whole array, so the size is n:

private static void buildHeap(int[] arr) {
  int n = arr.length;
  for (int i = n / 2 - 1; i >= 0; i--) {
    sink(arr, i, n);
  }
}

Because sink now enforces the max-heap order, this same loop produces a max-heap.

sortdown and heapSort

The sort has two phases. The first is buildHeap. The second is the emptying we traced by hand: swap the root to just past the heap, shrink the heap, and sink the new root, until one element is left. We call this phase sortdown, because it shrinks the heap by one element per pass until the heap is empty.

private static void sortdown(int[] arr) {
  for (int end = arr.length - 1; end > 0; end--) {
    swap(arr, 0, end);  // the root (largest) moves just past the heap
    sink(arr, 0, end);  // restore the heap over the first end slots
  }
}

In each turn, end is two things. It is the slot where the largest value goes, and it is the new size of the heap. After swap(arr, 0, end), the heap is the first end elements, so sink(arr, 0, end) restores exactly that region and leaves the finished tail alone. When end reaches 0, one element is left, already in place.

Heapsort runs the two phases in order:

public static void heapSort(int[] arr) {
  buildHeap(arr);   // rearrange the array into a max-heap
  sortdown(arr);    // empty the heap, laying the values down in order
}

The next section traces both phases on our array.