# 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++];
}

}
}

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?

• Space usage looks like O(N log N) to me.
– cHao
Commented Jan 20, 2015 at 2:37

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

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.

• I guess we could use JNI but that would be a lot of work for a proof of concept sorting algorithm. Commented Jan 21, 2015 at 2:09