HeapSort

    public class HeapSort{
        public void sort(int[] arr) {
            int N = arr.length;
            for(int k = N/2; k >= 1; k --) {
                sink(arr, k, N);   //make heap
            }
            while(N > 1) {
                exch(arr, 1, N--);
                sink(arr, 1, N);
            }
        }
        private void sink(int[] arr, int i, int N) {
            while(i *2 <= N) {
                int j =  i * 2;
                if(j < N && arr[j - 1] < arr[j]) j++;
                if(arr[i - 1] >= arr[j - 1]) break;
                exch(arr, i, j);
                i = j;
            }
        }
        private void exch(int[] arr, int i, int j) {
            int tmp = arr[i -1];
            arr[i-1]=arr[j-1];
            arr[j-1]=tmp;
        }
    }