Merge

Task 1: Your task is to write the static method merge thatcombines two sorted arrays into one sorted array.

The merge method requires two parameters, each of which is a sorted array. The method creates and returns a new sorted array that includes all the integers that are in the two given arrays.

public static int[] merge(int[] a, int[] b)

For example, if we call merge and provide the following two arrays as parameters:

1

3

5

6

and

0

2

4

7

8

9

the method returns the array:

0

1

2

3

4

5

6

7

8

9

Do not assume anything about the relative sizes of the two given arrays.

Do not use a sorting algorithm to put the new array in the proper order. Instead, take advantage of the fact that the two given arrays are already sorted. In other words, your merge method must be O(n).

Test your merge method when done. The test method should print the two starting arrays as well as the array returned by merge.

Task 2: Using the method from Part I as a model, write another merge method. This one has three parameters: an array, a start index, a mid index and an end index.

public static void merge(int[] a, int s, int mid, int end)

The goal of the method is the same, except you are only given one array. The three indices identify two contiguous array ranges:

range 1: indices start to mid

range 2: indices mid+1 to end

The numbers in each range are sorted. This method merges the two ranges so that all of the numbers between indexes start and end are sorted. The method does not return a new array, but may create a temporary one.

NOTES:

Do not assume that start is 0 and end is a.length-1.

Youll need to create a temporary array inside the merge method in order for the method to work. Be sure to copy the integers back unto the original a array before the method ends.

Task 3: Add the following methods to your class:

public static void mergeSort(int[] a) {

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

}

private static void mergeSort(int[] a, int s, int end) {

if (s < end) {

int mid = (start+end)/2;

mergeSort(a, start, mid);

mergeSort(a, mid+1, end);

merge(a, start, mid, end);

}

}

Test the mergeSort method with an array of random integers. If you wrote the merge method correctly in Task 2, the mergeSort method should sort the integers into ascending order.

TEST YOUR METHODS!!!