3
\$\begingroup\$

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?

\$\endgroup\$
  • 2
    \$\begingroup\$ Space usage looks like O(N log N) to me. \$\endgroup\$ – cHao Jan 20 '15 at 2:37
2
\$\begingroup\$

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, ..., ...);
}
\$\endgroup\$
0
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ I guess we could use JNI but that would be a lot of work for a proof of concept sorting algorithm. \$\endgroup\$ – horvste Jan 21 '15 at 2:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.