I need to use a merge sort in java to sort two arrays that will then be searched
ID: 3837162 • Letter: I
Question
I need to use a merge sort in java to sort two arrays that will then be searched by a binary search. I have a merge sort and binary sort written separately but am having trouble linking them. I need the outputs of the merge sort to be the inputs for the binary search.
The arrays are read in from a text file through the main and come like this:
5 2
4
7
12
89
102
92
89
The first number on the first line tells how many rows are in the first array (data) and the second tells how many are in the second array (query).
The binary search is this:
public static boolean binarysearch(int[] inputArray, int key) {
int start = 0;
int end = inputArray.length - 1;
while (start <= end) {
int middle = (start + end) / 2;
if (key == inputArray[middle]) {
return true;}
if (key < inputArray[middle]) {
end = middle - 1;}
else {start = middle + 1;}}
return false;}
The merge sort I have so far is this:
public class MergeSort {
//binary (sorted first)
private static double[] merge(double[] x, double[] y) {
double[] z = new double[x.length + y.length];
int i = 0, j = 0;
for (int k = 0; k < z.length; k++) {
if (i >= x.length) z[k] = y[j++];
else if (j >= y.length) z[k] = x[i++];
else if (x[i] <= y[j]) z[k] = x[i++];
else z[k] = y[j++];
}
return z;
}
public static double[] mergesort(double[] input) {
int n = input.length;
if (n <= 1) return input;
double[] x = new double[n/2];
double[] y = new double[n - n/2];
for (int i = 0; i < x.length; i++)
x[i] = input[i];
for (int i = 0; i < y.length; i++)
y[i] = input[i + n/2];
return merge(mergesort(x), mergesort(y));
}
As you can see, it's meant for doubles (it was written for something else). How do I modify my code so the merge methods take in arrays and so that the return parameters give the right inputs for the binary sort.
Explanation / Answer
Here merge function merges two sorted arrays and returns one array. But those array are of data type double.
Where as in Binary search, input taken by the function in one integer array.
Here is what you can do :
1) Use integer data type for merge sort and merge functions
2) give final sorted array to the binary search function.
Merge sort is procedure that divides the array and merge is the procedure that merges two sorted arrays.
I have updated merge sort, merge and binary seach :
public static int[] mergesort(int[] input) {
int n = input.length;
if (n <= 1) return input;
int[] x = new int[n/2];
int[] y = new int[n - n/2];
for (int i = 0; i < x.length; i++)
x[i] = input[i];
for (int i = 0; i < y.length; i++)
y[i] = input[i + n/2];
return merge(mergesort(x), mergesort(y));
}
private static int[] merge(int[] x, int[] y) {
int[] z = new int[x.length + y.length];
int i = 0, j = 0;
for (int k = 0; k < z.length; k++) {
if (i >= x.length) z[k] = y[j++];
else if (j >= y.length) z[k] = x[i++];
else if (x[i] <= y[j]) z[k] = x[i++];
else z[k] = y[j++];
}
return z;
}
Binary search remain as it is :
public static boolean binarysearch(int[] inputArray, int key) {
int start = 0;
int end = inputArray.length - 1;
while (start <= end) {
int middle = (start + end) / 2;
if (key == inputArray[middle]) {
return true;}
if (key < inputArray[middle]) {
end = middle - 1;}
else {start = middle + 1;}}
return false;
}
Now suppose there is some array arr , you want to sort it and then pass it to binary search .
here is what you can do :
1) fetch arrays from file :
arr1 and arr2 are two fetched array from file.
2) apply merge sort on them indivisually :
arr1 = mergesort(arr1);
arr2 = mergesort(arr2);
3) Now we have two sorted arrays, we can merge them and create one sorted array from those two using merge() function :
int arr[] = merge (arr1, arr2);
4) Now that we have one sorted array we can pass it to the binary search function :
binarySearch(arr, 5) ; // 5 is a key to be found in array.
If you have any doubts, you can ask in comment section.
Edit :
-> fetch two arrays from file in arr1 and arr2. where arr1 is data array and arr 2 is query array.
--> sort arr1 using procedure given above. ( mergesort(arr1) )
--> Use for loop to search for each element like this :
for(i=0; i<arr2.size; i++){
bool result = binarysearch(arr1, arr2[1]);
print result;
}
I have just mentioned psuedo code. you can change it according to language you are using for implementation.
If you have any doubts, you can ask in comment section.