2
\$\begingroup\$

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

}
```
\$\endgroup\$
3
  • 2
    \$\begingroup\$ 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. \$\endgroup\$
    – ggorlen
    Jan 29, 2023 at 23:09
  • \$\begingroup\$ To avoid redundance private static int[] mergeSort(int[] numArray) {return mergeSort(subArray, false);} \$\endgroup\$
    – convert
    Jan 29, 2023 at 23:11
  • \$\begingroup\$ 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. \$\endgroup\$
    – cyberbrain
    Mar 1, 2023 at 9:45

1 Answer 1

1
\$\begingroup\$

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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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