Merge Sort Implementation: Space Usage

Question

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?

Answer 1

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, ..., ...);
}

Answer 2

You can use inbuilt functions to copy arrays.

    int[] newArrLeft = new int[arr.length / 2];
    int[] newArrRight = new int[arr.length - (arr.length / 2)];

    System.arraycopy(arr, 0, newArrLeft, 0, newArrLeft.length);
    System.arraycopy(arr, newArrLeft.length, newArrRight, 0, newArrRight.length);

I tested above code and it is working fine.

The problem with this implementation is it creates too many array objects in memory.

In C, we can develop in-place merge sort using pointers and passing start and end of the array. I am not sure if same can be done in Java.

Also there was question which is related to merger sort and this answer seems relevant- https://codereview.stackexchange.com/a/64712/63397

Actually JDK uses modified version of merge sort called timsort. That algorithm is very interesting but hard to understand. It is very fast if input array has some parts which are already sorted.