Implement the merge method below import java.util.Arrays; public class MergeSort
ID: 3695511 • Letter: I
Question
Implement the merge method below
import java.util.Arrays;
public class MergeSort {
public static void main(String[] args) {
int size = 50;
int[] x = new int[size];
for(int i=0; i<size; i++) {
x[i] = (int) (Math.random() * size);
}
System.out.println(Arrays.toString(x));
System.out.println(Arrays.toString(new MergeSort().sort(x)));
}
static final int MIN_SIZE = 10;
int[] sort(int[] in) {
int[] out;
int length = in.length;
if(length <= MIN_SIZE) {
out = new SelectionSort(in).sort();
}
else {
int len1 = length/2, len2 = length - len1;
int[] in1 = new int[len1], in2 = new int[len2];
System.arraycopy(in, 0, in1, 0, len1);
System.arraycopy(in, len1, in2, 0, len2);
out = merge(sort(in1), sort(in2));
}
return out;
}
// merge the two sorted arrays in1 and in2 and return the result
int[] merge(int[] in1, int[] in2) {
// TODO
}
}
class SelectionSort {
int[] array;
SelectionSort(int[] array) { this.array = array; }
int[] sort() {
for(int i=0; i<array.length; i++) {
int j = minIndex(i);
if (i != j) {
swap(i, j);
}
}
return array;
}
void swap(int i, int j) {
int temp = array[i];
array[i] = array[j];
array[j] = temp;
}
// return the index with min value from index "start" in "array"
int minIndex(int start) {
int ret = start;
for(int i=start+1; i<array.length; i++) {
if(array[ret] > array[i]) {
ret = i;
}
}
return ret;
}
}
Explanation / Answer
int[] merge(int[] in1, int[] in2) {
int[] C = new int[in1.length + in2.length];
int in1Index = 0;
int in1Count = in1.length;
int cIndex = C.length;
// Copy over array in1 (but only if the element is less than in2)/>
// What if it isn't less than in2?
while (in1Index < in1Count){
if(in1[in1Index] < in2[in1Index]){
C[in1Index]= in1[in1Index];
}
in1Index++;
}//end while
// Copy over in2 starting where array in1 left off
// But be sure to read the part about copying in1 above.
for(int in2Index = 0; in2Index < in2.length; in2Index++){
C[aIndex] = in2[bIndex];
in1Index++;
}
return C;
}