Merge Sort Implementation: Space Usage

I have made a merge sort algorithm but am unsure of the 'Space Usage' of the algorithm.

public class Sorting {

    public static void mergeSort(int[] arr) {
        if (arr.length == 1) {
            return;
        }
        int[] newArrLeft = new int[arr.length / 2];
        int[] newArrRight = new int[arr.length - (arr.length / 2)];
        int currentRight = 0;
        for (int i = 0; i < arr.length; i++) {
            if (i < arr.length / 2) {
                newArrLeft[i] = arr[i];
            } else {
                newArrRight[currentRight++] = arr[i];
            }
        }
        mergeSort(newArrLeft);
        mergeSort(newArrRight);
        merge(newArrLeft, newArrRight, arr);

    }

    private static void merge(int[] arrLeft, int[] arrRight,
            int[] sortedValuesArr) {
        int currentLeft = 0;
        int currentRight = 0;
        int currentSorted = 0;
        while (currentLeft < arrLeft.length && currentRight < arrRight.length) {
            if (arrLeft[currentLeft] < arrRight[currentRight]) {
                sortedValuesArr[currentSorted++] = arrLeft[currentLeft++];
            } else {
                sortedValuesArr[currentSorted++] = arrRight[currentRight++];
            }
        }

        while (currentLeft < arrLeft.length) {
            sortedValuesArr[currentSorted++] = arrLeft[currentLeft++];
        }
        while (currentRight < arrRight.length) {
            sortedValuesArr[currentSorted++] = arrRight[currentRight++];
        }

    }
}

I am specifically inquiring about:

int[] newArrLeft = new int[arr.length / 2];
int[] newArrRight = new int[arr.length - (arr.length / 2)];
int currentRight = 0;
for (int i = 0; i < arr.length; i++) {
    if (i < arr.length / 2) {
        newArrLeft[i] = arr[i];
    } else {
        newArrRight[currentRight++] = arr[i];
    }
}

Is the above code wasting space? Is there a better implementation?

Is the above code wasting space?

Yes. As @cHao pointed out in a comment, you are using \$O(N log N)\$ space. You can do mergesort in \$O(N)\$ space.


Is there a better implementation?

Yes. The biggest problem wrt both time and space efficiency is that you are unnecessarily allocating and copying auxiliary arrays.

You can instead create 1 auxiliary array and pass the same array around together with the interval to be sorted, or merged.

Your methods would look like these, some implementation left exercise :

public static void mergeSort(int[] arr) { 
    mergeSortBetween(arr, new int[arr.length], 0, arr.length -1);
}

private static void mergeSortBetween(int[] arr, int[] aux, 
    int startIndex, int endIndex) {
    if (...) {
        return;
    }
    //...
    mergeSortBetween(arr, aux, startIndexLeft, endIndexLeft);
    mergeSortBetween(arr, aux, startIndexRight, endIndexRight);
    merge(arr, aux, 
        startIndexLeft, endIndexLeft, 
        startIndexRight, endIndexRight);
}

private static void mergeBetween(int[] arr, int[] aux, 
    int startIndexLeft, int endIndexLeft, 
    int startIndexRight, int endIndexRight) {
    // only need to merge consecutive chunks
    assert startIndexRight = endIndexLeft + 1;
    //merge into aux
    while (currentLeft < startIndexLeft && currentRight < endIndexRight) {
        if (...)
            aux[...] = arr[...]
        else 
            aux[...] = arr[...]
    }
    while (currentLeft < endIndexLeft) {
        aux[...] = arr[...]
    }
    while (currentRight < endIndexRight) {
        aux[...] = arr[...]
    }

    //copy merged values back into arr
    System.arraycopy(aux, ..., arr, ..., ...);
}

StackExchange Code Review Q#78070, answer score: 2