We discussed the mergesort yesterday:
mergesort the leftHalf
mergesort the rightHalfmergeTheTwoHalvesIntoTheOriginalArray
This can be done in many ways for example copy each half into a new array:
if ...base case...
intleft = copy of the left side;
intright = copy of the right side;
This will use more space but is still very fast. This is the easiest way and will be all that I require.
One possible way to make the merge method work well in this situation is to merge directly into the array you want to put the values into (DO NOT return a new array and then copy that over
destination contains all of the elements of a and b, and is sorted.
a is sorted, b is sorted
destination.length == a.length + b.length
There are more advanced ways that would be better suited for extra credit. You can think of ways to optimize your mergesort if you feel like entering the merge sort competition which will be put up later.
Write the mergesort in your git directory:
->public static void mergesort(intary)