The following is my code for Merge Sort in JAVA, but the output is not expected.
given input is [49, 1, 3, 200, 2, 4, 70, 5]
The output is :
Merge sort : [2, 4, 49, 1, 3, 70, 5, 200]
Which the number is not sorted. I believe the problem is in the merge method. Can anyone help?
merge_sort method:
private static int[] merge_sort(int[] unsorted_array) {
if (unsorted_array.length < 2) {
return unsorted_array;
}
int mid = unsorted_array.length / 2;
int[] first_array = new int[mid];
int[] second_array = new int[unsorted_array.length - mid];
//Copy element to first and second array.
for (int i = 0; i < mid; i ++) {
first_array[i] = unsorted_array[i];
}
for (int i = 0; i < second_array.length; i++) {
second_array[i] = unsorted_array[mid + i];
}
merge_sort(first_array);
merge_sort(second_array);
int[] sorted_array = merge(first_array, second_array);
return sorted_array;
}
merge method:
private static int[] merge(int[] first_array, int[] second_array) {
int[] result = new int[first_array.length + second_array.length];
int index_result = 0;
int index_first = 0;
int index_second = 0;
while (index_first < first_array.length && index_second < second_array.length) {
if (first_array[index_first] < second_array[index_second]) {
result[index_result] = first_array[index_first];
index_first++;
} else {
result[index_result] = second_array[index_second];
index_second++;
}
index_result++;
}
while (index_first < first_array.length) {
result[index_result] = first_array[index_first];
index_result++;
index_first++;
}
while (index_second < second_array.length) {
result[index_result] = second_array[index_second];
index_result++;
index_second++;
}
return result;
}
You've made a very simple mistake.
Those two following lines are wrong in your code:
merge_sort(first_array);
merge_sort(second_array);
You should write those two lines as follows:
first_array = merge_sort(first_array);
second_array = merge_sort(second_array);
cause, your merge_sort() method returns a sorted array. It does not sort in place the unsorted_array parameter. Rather, it returns the sorted elements in a newly created sorted_array. So, you would get the sorted result from return value of merge_sort() method and then, you should merge them. Rather than doing that, you were just merging two unsorted arrays.
Its not necessary, but you could write as follows for clarification:
int[] sorted_first_array = merge_sort(first_array);
int[] sorted_second_array = merge_sort(second_array);
// and then merge
int[] sorted_array = merge(sorted_first_array, sorted_second_array);
// then return
return sorted_array;
[P.S.]: When you are coding in java, please use java variable and method naming convention. Its easier to read code when you're following convention.