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

Question

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;
  }

}
```

Answer 1

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.