Sorting Algorithms

class BubbleSort {
    public void bubbleSortAsc(int[] array) {
        for (int i = 0; i < array.length - 1; i++) {
            for (int next = 1; next < array.length - i; next++) {
                int currentVal = array[next - 1];
                int nextVal = array[next];
 
                if (currentVal > nextVal) {
                    array[next - 1] = nextVal;
                    array[next] = currentVal;
                }
            }
        }
    }
}

class MergeSort {
    
    private void mergeSort_merge(int[] array, int[] tempArray, int left, int mid, int right) {
        // Copy the sub-array from array defined by left and right into the same indexes of tempArray.
        for (int i = left; i <= right; i++) {
            tempArray[i] = array[i];
        }
        
        // Separate the array at the index "mid" into two sub-arrays.
        // NOTE: mid is the last index of the first array (and mid + 1 is the first of the second).
        // Iterate through the elements of two halves and add the elements in order over the original
        // values in array. Stop when either of the two halves are empty.
        int leftPointer = left;
        int rightPointer = mid + 1;
        int addedPointer = left;
        while (leftPointer <= mid && rightPointer <= right) {
            if (tempArray[leftPointer] <= tempArray[rightPointer]) {
                array[addedPointer] = tempArray[leftPointer];
                leftPointer++;
            } else {
                array[addedPointer] = tempArray[rightPointer];
                rightPointer++;
            }
            addedPointer++;
        }
        
        // Just add all of the remaining elements of the array that wasn't emptied.
        // This could be either the first or second half so we have to do both.
        int remainingPointer = leftPointer <= mid ? leftPointer : rightPointer;
        for(; addedPointer <= right; addedPointer++, remainingPointer++) {
            array[addedPointer] = tempArray[remainingPointer];
        }
    }
    
    private void mergeSortAsc(int[] array, int[] tempArray, int left, int right) {
        if (left >= right) {
            // This occurs for the cases(*) shown below.
            return;
        }
 
        // Find the mid part of this array.
        // Integer devision rounds down, so:
        // if (left + right) is odd (array size is even)
        //  then mid points to the lower of the middle index.
        // If (left + right) is even (array size is odd)
        //  then mid points to the middle index.
        int mid = (left + right) / 2;
        
        // Recursive calls on both the left and right sub-arrays (assuming that mid is the
        // end of the first array, and (mid + 1) is that of the second).
        // * left == mid if the input array length was 2 (left = mid = 0).
        mergeSortAsc(array, tempArray, left, mid);
        // * (mid + 1) == right if the input array length was 2 (mid = 0 -> mid + 1 = right = 1).
        // * (mid + 1) == right if the input array is of length 3 (mid = 1 -> mid + 1 = right = 2).
        mergeSortAsc(array, tempArray, (mid + 1), right);
 
        // Given the above cases(*), mergeSort_merge is only called with arrays of size >= 2
        // Note: mergeSort_merge must take mid as the start and end pointers of the first array
        // as all recursive calls were made with this being the case and so have been
        // sorted accordingly.
        mergeSort_merge(array, tempArray, left, mid, right);
    }
    
    public void sortArray(int[] unsortedArray) {     
        mergeSortAsc(unsortedArray, new int[unsortedArray.length], 0, (unsortedArray.length - 1));
    }
}

class Solution {
    private void restructureHeap(int[] array, int p, int length) {
        // p is the index that references the parent node of 1-2 child nodes.
        // This *should* reference be the greatest value of all three.
        // We need to determine if this is the case and swap it the parent value
        // with the largest child value if necessary.
        // Because the child node may have been the parent of 1-2 other nodes itself
        // we then need to call this method recursively on that node as well.
        
        // Note that the children of any node is given by (2 * p) + 1
        // and (2 * p) + 2.
        
        int pVal = array[p];
        int c1 = (2 * p) + 1;
        int c2 = (2 * p) + 2;
        int swap = p;
        
        if (c1 < length && array[c1] > array[swap]) {
               swap = c1;
        }
        
        if (c2 < length && array[c2] > array[swap]) {
               swap = c2;
        }
        
        if (p != swap) {
            array[p] = array[swap];
            array[swap] = pVal;
            
            restructureHeap(array, swap, length);
        }
    }
    
    private void heapSortAsc(int[] array) {
        // Restructure heap at the from the mid-point down.
        for (int p = (array.length / 2) - 1; p >= 0; p--) {
            restructureHeap(array, p, array.length);
        }
        
        // For each element, excluding those that have been "retired" to the end
        // of the array.
        // - Swap the end with the last value
        // - restructure from just the first index as that is out of order.
        for (int length = array.length; length > 0; length--) {
            int swap = array[0];
            array[0] = array[length - 1];
            array[length - 1] = swap;
            
            int newlength = length - 1;
            restructureHeap(array, 0, newlength);
        }
        
    }
    
    public int heightChecker(int[] heights) {     
        int count = 0;
        int[] heightsSorted = Arrays.copyOf(heights, heights.length);
        heapSortAsc(heightsSorted);
        
        for (int i = 0; i < heights.length; i++) {
            if (heights[i] != heightsSorted[i]) {
                count++;
            }
        }
        
        return count;
    }
}