Scenario

Merge sorting is one of the fastest sorting techniques. It is used in many bundled libraries and APIs. In this activity, we will write an algorithm in Java to sort an array using merge sort.

Aim

Use the pseudocode shown in Snippet 2.11 and Snippet 2.12 to implement the full merge sort algorithm in Java.

Your MergeSort class should contain 3 methods, other than the main() stub.

mergeSort(array, start, end) if(start < end) midPoint = (end - start) / 2 + start mergeSort(array, start, midPoint) mergeSort(array, midPoint + 1, start) merge(array, start, midPoint, end)

^{Snippet 2.11: Recursive merge sort}

merge(array, start, middle, end) i = start j = middle + 1 arrayTemp = initArrayOfSize(end - start + 1) for (k = 0 until end-start) if (i <= middle && (j > end || array[i] <= array[j])) arrayTemp[k] = array[i] i++ else arrayTemp[k] = array[j] j++ copyArray(arrayTemp, array, start)

^{Snippet 2.12: Merge Psuedocode}

merge(array) merge(array, start, end)

Steps for Completion

1. Start from the mergeSort() method, which splits the array in two, recursively sorts both, and merges the result.
2. Then, implement the merge method, which merges both ends of the split array into another space.
3. After the merge is done, copy the new array back in place of the input array.

Tasks

The mergeSort() method handles a sorted array as a parameter and an array with identical elements.

The mergeSort() method handles sorting even and odd elements

The mergeSort() method handles sorting an empty array and an array with one element.

public class MergeSort {

// Write your code here public static void mergeSort(int []array, int start, int end){

if(start < end){

int midPoint = (end - start) / 2 + start;

mergeSort(array, start, midPoint);

mergeSort(array, midPoint + 1, end);

merge(array, start, midPoint, end);

}

}

public static void merge(int []array, int start, int middle, int end){

int i = start;

int j = middle + 1;

int arrayTemp[] = new int[end - start + 1];

for (int k = 0;k<=end-start;k++){

if (i <= middle && (j > end || array[i] <= array[j])) {

arrayTemp[k] = array[i];

i++;

}

else {

arrayTemp[k] = array[j];

j++;

}

} for(int k = start, l = 0;k<=end;k++, l++) { array[k] = arrayTemp[l]; }

}

public static void merge(int []array){

mergeSort(array,0, array.length-1);

}

public static void main(String[] args) {

/*

* This main method is a stub.

* It does nothing.

* Feel free to write your own code to test your implementation.

* In this case, we have nothing actionable in here, just this comment block, so the JVM should rapidly lose interest and move on to the rest of your code.

*/

int a[] = {2,3,4,52,2,3,4,1}; merge(a); for(int i =0;i { System.out.print(a[i] + " "); } System.out.println(); }

}