Question

HW58.1. Array Merge Sort You've done merge (on Lists), so now it's time to do merge sort (on arrays). Create a public non-final class named Mergesort that extends Merge. Implement a public static method int[] mergesort(int[] values) that returns the input array of ints sorted in ascending order. You will want this method to be recursive, with the base case being an array with zero or one value. If the passed array is null you should return null. If the passed array is empty you should return an empty array. You do not have to sort the array in place, but the returned array does not have to be a copy. To help you your parent class Merge provides two useful class methods: 1. int[] merge(int[] first, int[] second): this merges two sorted arrays into a second sorted array. If either array is null it returns null, so you should not call it on a null array. 2. int[] copyOfRange(int[] original, int from, int to): this acts as a wrapper on Arrays.copyOfRange, accepting the same arguments and using them in the same way. (You can't use java.util.Arrays in this problem for reasons that will become obvious if you inspect the rest of the documentation...) Note that the test code will test that you call merge an appropriate number of times, so you should call it to join single-element arrays together.

Answer 1

 import java.util.Arrays; class Merge { public static int[] merge(int[] first, int[] second) { int[] result = new int[first.length + second.length]; int i = 0, j = 0, k = 0; int n1 = first.length; int n2 = second.length; while(i < n1 && j < n2) { if(first[i] <= second[j]) { result[k] = first[i]; i++; } else { result[k] = second[j]; j++; } k++; } while( i < n1) { result[k] = first[i]; k++; i++; } while( j < n2) { result[k] = second[j]; k++; j++; } return result; } public static int[] copyOfRange(int[] original, int from, int to) { return Arrays.copyOfRange(original, from, to); } } public class MergeSort extends Merge { public static int[] mergesort(int[] values) { if (values == null || values.length <= 1) { return values; } int m = values.length/2; int[] left = copyOfRange(values, 0, m); int[] right = copyOfRange(values, m, values.length); left = mergesort(left); right = mergesort(right); if (left != null && right != null) return merge(left, right); else { if (left == null) return right; else return left; } } public static void main(String []args){ int arr[] = {12, 11, 13, 5, 6, 7}; MergeSort ms = new MergeSort(); int[] res = ms.mergesort(arr); for(int i = 0; i < res.length; i++) System.out.print(res[i] + " "); } } 

I have also provided Merge class to help you with that. I have also added helper main method to allow you to execute code. You can remove main method as that is not asked in the class.

Sample exeucteion

 5 6 7 11 12 13