JAVA

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.

Grading

Complete each task listed below. Each task contains automated checks which are used to calculate your grade. When you have completed each task by clicking the checkbox, open the task list panel on the left navigation bar and click the "Submit" button.

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.

Given Code:

public class MergeSort {

// Write your code here

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.

*/

}

}