package sort;

/**
 * Contains implementations for the Merge Sort algorithm.
 */
public class MergeSort {
    /**
     * Recursive Merge Sort algorithm implementation.
     * Efficiency: O(n log n), not in-place.
     * @param arr array of elements to be sorted.
     * @param left left bound index.
     * @param right right bound index.
     */
    public void mergeSortRecursive(int[] arr, int left, int right) {
        if(right <= left) {
            return;
        }
        int mid = (left + right) / 2;
        mergeSortRecursive(arr, left, mid); // recurse left partition
        mergeSortRecursive(arr, mid + 1, right); // recurse right partition
        merge(arr, left, right, mid); // sort disassembled partitions
    }

    /**
     * Helper method used within the Merge Sort algorithm.
     * @param arr the array to be merged into.
     * @param left left bound index.
     * @param right right bound index.
     * @param mid midpoint between left and right index partitions.
     */
    public void merge(int[] arr, int left, int right, int mid) {
        int leftCount = (mid + 1) - left;
        int rightCount = right - mid;
        int[] leftArr = new int[leftCount];
        int[] rightArr = new int[rightCount];
        for(int i = 0; i < leftCount; i++) {
            leftArr[i] = arr[left + i];
        }
        for(int i = 0; i < rightCount; i++) {
            rightArr[i] = arr[mid + 1 + i];
        }
        int l = 0, r = 0, iter = left;
        while(l < leftArr.length && r < rightArr.length) {
            if(leftArr[l] < rightArr[r]) {
                arr[iter++] = leftArr[l++];
            }
            else {
                arr[iter++] = rightArr[r++];
            }
        }
        while(l < leftArr.length) {
            arr[iter++] = leftArr[l++];
        }
        while(r < rightArr.length) {
            arr[iter++] = rightArr[r++];
        }
    }
}