Merge Sort

Write a recursive program MergeSortDemo.java that demonstrates the Merge Sort algorithm. The program should include a static method sort() that takes an int[] array as a parameter and sorts it using a merge sort strategy. An accompanying static method merge() can be used as part of that strategy. The merge() method has three int[] array parameters: the first two parameters are smaller arrays that are already sorted, and the third is the larger array into which those smaller arrays will be merged.

The Merge Sort algorithm is summarized here.

1. Begin with an unsorted array of values.

2. Split the array into two approximately equal halves: the "left side" and the "right side".
   There are a couple of different ways that you can do this. One is to use the arraycopy method:

   System.arraycopy(sourceArray, initialSourceIndex, destinationArray, initialDestinationIndex, numberOfItemsToCopy);

   Thus, to make a copy of the first half of a larger array into a smaller array holding just those values:

   // given an original array arr
   int middleIndex = arr.length / 2; 
   int copySize = middleIndex;
   int[] firstHalf = new int[copySize];
   // Now copy the first half of the original array into the new array
   System.arraycopy(arr, 0, firstHalf, 0, copySize);

3. Each half is recursively split into successively smaller "left" and "right" sides until each side has a length of 0 or 1 (the base case). This element (or non-element) is considered sorted. No merging needs to happen, and no value needs to be returned.

4. Upon returning from the base case, the left and right sides need to be merged. As long as there are values in both side to be merged, continue copying whichever value is smallest into the next location in the original array.

5. Once all of the number have been copied from either the left side or ride side, copy the values from the remaining list into the original array. The (sub-) array is now sorted.