Heap Sort

1void heapSort(int[] arr) {2  int n = arr.length;3  for (int i = n/2-1; i >= 0; i--) siftDown(arr, i, n);  // build max-heap4  for (int end = n-1; end > 0; end--) {  // shrink the heap5    int temp = arr[0]; arr[0] = arr[end]; arr[end] = temp;  // max to the end6    siftDown(arr, 0, end);  // restore heap7  }8}9void siftDown(int[] arr, int root, int end) {10  while (2*root+1 < end) {  // while a child exists11    int child = 2*root+1;12    if (child+1 < end && arr[child+1] > arr[child]) child++;  // pick larger child13    if (arr[root] >= arr[child]) break;  // heap order ok14    int temp=arr[root]; arr[root]=arr[child]; arr[child]=temp; root=child;  // swap down15  }16}