Heap Sort

class Solution {
    // O(NlogN) Time & O(1) Space
    // Use Max Heap for ascending order in the end
    public static void sort(int[] arr) {
        // Assume that array upto i-1 is in heap format
        // Parent Index -> (i-1)/2
        for (int i = 1; i < arr.length; i++) {
            // Up heapify LogN
            if (arr[i] > arr[(i - 1) / 2]) {
                int j = i;
                while (j != 0 && arr[j] > arr[(j - 1) / 2]) {
                    swap(arr, (j - 1) / 2, j);
                    j = (j - 1) / 2;
                }
            }
        }
        // Now the array is in complete heap format
        for (int i = arr.length - 1; i >= 0; i--) {
            // Remove biggest element from heap and put it in the end
            swap(arr, 0, i);
            // Down heapify LogN
            if (arr[0] < arr[1] || arr[0] < arr[2]) {
                int j = 0;
                while (j < i && (2 * j + 1 < i && arr[j] < arr[2 * j + 1])
                        || (2 * j + 2 < i && arr[j] < arr[2 * j + 2])) {
                    if (arr[2 * j + 1] > arr[2 * j + 2]) {
                        swap(arr, j, 2 * j + 1);
                        j = 2 * j + 1;
                    } else {
                        swap(arr, j, 2 * j + 2);
                        j = 2 * j + 2;
                    }
                }
            }
        }
    }

    public static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}