you will implement divide and conquer algorithms: merge sort . For merge sort, you will just implement the algorithm on an array of ints. I have provided the pseudo code for algorithms. You will need to handle cases of all sizes, not just powers of 2.

Implement Merge Sort

Create a class called MergeSorter in the divideandconquer package. This class will implement merge sort on an array of ints. Implement the following method with the exact signature below. You will need to create private helper methods that do most of the work.

public static void mergeSort(int[] arr)

 

This method sorts the int[] arr using the merge sort algorithm described in the pseudocode above.

Merge Sort merge Sort (arr, start, end) if start>=end return mid midpoint of arr merge Sort (arr, start, mid) mergeSort (arr, mid+1, end) //merge the two parts. merge (arr, start, mid, end) merge (arr, start, mid, end) leftSize = mid rightSize = start + 1; end - mid; left [0..leftSize] right [0..rightSize] for leftIndex-0 to leftSize left [leftIndex] = for rightIndex=0 to rightSize leftIndex = 0 right Index = 0 right [right Index] arr [mid+right Index-1] left [leftSize] = MAX right [rightSize] = MAX arr [start+leftIndex] else for mergeIndex-start to end if left [leftIndex] right [rightIndex] arr [merge Index] = left [left Index] leftIndex = leftIndex+1 arr [merge Index] = right [rightIndex] right Index = rightIndex+1