# Merge Sort with Minimum Sufficient Variables, Verbosity and better Space Complexity

The majority of merge sort implementations searched online are provided with unnecessary variables and code lines. Here is an attempt to reduce that. However, does passing back the subArray as return types around cause any extra overhead on space complexity due to the temporary auxiliary space requirements for the return values to keep on the recursive method call stack?

import static java.lang.System.out;

import java.util.Arrays;

/**
* @author thomas
*/
public class MergeSort {

public static void main(String[] args) {
int[] numArray = new int[]{4, 7, 2, 8, 1, 0, 2, 5, -4, 3};
out.println("Original array before sorting: " + Arrays.toString(numArray));
out.println("Ascending Sorted Array: " + Arrays.toString(mergeSort(numArray)));
out.println("Original array after sorting: " + Arrays.toString(numArray));
out.println("Descending Sorted Array: " + Arrays.toString(mergeSort(numArray, true)));
}

private static int[] mergeSort(int[] numArray) {
int[] subArray = Arrays.copyOfRange(numArray, 0, numArray.length);
return partition(subArray, false);
// return subArray; // return explicitly here with just calling the partition(subArray, false) and void return types for all the subsequent methods signature of partition() and onwards;
}

private static int[] mergeSort(int[] numArray, boolean isDescending) {
int[] subArray = Arrays.copyOfRange(numArray, 0, numArray.length);
return partition(subArray, isDescending);
// return subArray; // return explicitly here with just calling the partition(subArray, isDescending) and void return types for all the subsequent methods signature of partition() and onwards;
}

private static int[] partition(int[] subArray, boolean isDescending) {
if (subArray.length < 2) {
return subArray;
}
int mid = subArray.length / 2;
int[] leftArray = Arrays.copyOfRange(subArray, 0, mid);
int[] rightArray = Arrays.copyOfRange(subArray, mid, subArray.length);
partition(leftArray, isDescending);
partition(rightArray, isDescending);
return merge(subArray, leftArray, rightArray, isDescending);
}

private static int[] merge(int[] subArray, int[] leftArray, int[] rightArray, boolean isDescending) {
int leftIndex = leftArray.length, rightIndex = rightArray.length;
int leftArrayIncrementer = 0, rightArrayIncrementer = 0, mergedArrayIncrementer = 0;
while (leftArrayIncrementer < leftIndex && rightArrayIncrementer < rightIndex) {
if (leftArray[leftArrayIncrementer] <= rightArray[rightArrayIncrementer]) {
subArray[mergedArrayIncrementer++] = isDescending ? rightArray[rightArrayIncrementer++] : leftArray[leftArrayIncrementer++];
} else {
subArray[mergedArrayIncrementer++] = isDescending ? leftArray[leftArrayIncrementer++] : rightArray[rightArrayIncrementer++];
}
}
while (leftArrayIncrementer < leftIndex) {
subArray[mergedArrayIncrementer++] = leftArray[leftArrayIncrementer++];
}
while (rightArrayIncrementer < rightIndex) {
subArray[mergedArrayIncrementer++] = rightArray[rightArrayIncrementer++];
}
return subArray;
}

}
$$$$

• A merge sort that copies the array for partitioning is terribly inefficient from a time complexity standpoint. I suggest you revisit whether those variables you're referring to (probably they're indices) really are necessary (spoiler: they are). Please cite what you're referring to. Jan 29, 2023 at 23:09
• To avoid redundance private static int[] mergeSort(int[] numArray) {return mergeSort(subArray, false);} Jan 29, 2023 at 23:11
• One of your mergeSort methods has the same signature (except the name of the method) as the partition method, so you should rename the partition to mergeSort and get rid of the existing mergeSort - the complete array copy is not really necessary I think. The other mergeSort method is just a convenience thingy, but as it is private, skip it and just specify the second parameter always. Mar 1, 2023 at 9:45

Is this code ready to ship?

No. Recommend you make some edits and resubmit it.

Here are my constructive criticisms.

The main() method is nice enough.

But it would be better to offer it as a junit @Test case.

I am reading the mergeSort definitions.

We see a pair of // return subArray... comments. I'm sure they were useful during manual testing.

Now that it's Review Time, the time has come to delete them.

DRY. The single-arg version should simply call mergeSort(numArray, false).

Both versions call Arrays.copyOfRange(), which is sort of disqualifying. The two big requirements for a merge sort are

1. elements must be ordered at the end
2. time complexity must be O(N log N)

You need to be passing around indexes and a pointer to same array, not giant newly allocated array slice copies.

Write a pair of unit tests, which sort arrays of size one-thousand and one-million. Note the ratio of elapsed times. Keep improving your implementation until N log N is predictive of the running time.

You wrote some more methods, but I see several .copyOfRange calls in partition so I'll wait for a resubmittal before I start studying them.

Overall?

Not yet read to merge to main`.