Complete your mergesort Java class (started during class today). Due at the start of next class.
You may want to consider breaking the merge phase into its own method, like the one below. You can then call the merge method from your recursive sort method to handle this phase of the sort.
/**
* Given an array of integers, this method looks at two subarrays contained
* within the array. Both subarrays should already be sorted. This method
* merges the two subarrays together so that they contain all of the elements
* from both subarrays in order.
*
* This method creates a temporary array that is the size of both subarrays.
* It uses the temporary array to store the elements so they may be written
* back to the original array in order, overwriting the elements that were
* there previously.
*
* @param a The array to merge. The merged elements should be written
* back to this array in order, overwriting what was there.
* @param left The index of the first element in the left subarray to merge.
* All other elements with index less than left are ignored.
* @param middle The first index of the right subarray to merge (also, the
* first element that is NOT part of the left subarray). This
* is the dividing line between the two subarrays.
* @param right The first index that is NOT part of the right subarray. All
* elements with index greater than or equal to right are
* not processed by this algorithm.
*
* Precondition: left is less than middle; middle is less than right;
* right is less than or equal to the length of a
* The elements from left to middle-1 are ordered; the elements
* from middle to right-1 are ordered.
* Postcondition: All elements from left to right-1 are ordered.
*/
public <T extends Comparable<? super T>> void merge(T[] a, int left, int middle, int right);
Hint: you cannot directly make an array of the generic type T
(due to the type erasure system used by Java). In order to make a new generic array, I suggest using the Array utility method copyOfRange
, like this:
T[] duplicate = Arrays.copyOfRange(a, left, right);
The line above would make a new generic array named duplicate
that has the same type as a
. It will contain all of the elements starting at left
and up to (but not including) right
(in other words, using the same range rules as your sort).
You'll also need to add this line to the top of your class file (underneath the package
declaration):
import java.util.Arrays;