# Merge Sort不正常工作。数组中的数字没有排序。

go评论47阅读模式

Merge Sort does not work properly. The numbers in array are not sorted

# 问题

merge_sort方法：

``````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];

//将元素复制到第一个和第二个数组中。
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方法：

``````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;
}
``````

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 &lt; 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 &lt; mid; i ++) {

first_array[i] = unsorted_array[i];
}

for (int i = 0; i &lt; 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 &lt; first_array.length &amp;&amp; index_second &lt; second_array.length) {

if (first_array[index_first] &lt; 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 &lt; first_array.length) {

result[index_result] = first_array[index_first];
index_result++;
index_first++;
}

while (index_second &lt; second_array.length) {

result[index_result] = second_array[index_second];
index_result++;
index_second++;
}

return result;
}
``````

# 答案1

``````first_array = merge_sort(first_array);
second_array = merge_sort(second_array);

int[] sorted_array = merge(first_array, second_array);
``````

``````private static void merge_sort(int[] unsorted_array, int low, int high) {

if (low == high) return;

int mid = low + (high - low) / 2;

merge_sort(unsorted_array, low, mid);
merge_sort(unsorted_array, mid+1, high);

merge(unsorted_array, low, mid, high);

}

``````

You are not using the sorted intermediate results to merge, instead using the original splitted arrays. Modify your code as below:

``````first_array = merge_sort(first_array);
second_array = merge_sort(second_array);

int[] sorted_array = merge(first_array, second_array);
``````

Also you don't need to create these intermediate arrays. You just have to pass the low, high pointers to your array to indicate the portions of the array you are sorting and merging.

Like :

``````private static void merge_sort(int[] unsorted_array, int low, int high) {

if (low == high) return;

int mid = low + ( high - low ) / 2;

merge_sort(unsorted_array, low, mid);
merge_sort(unsorted_array, mid+1, high);

merge(unsorted_array, low, mid, high);

}
``````

where `high` is inclusive and you call this like : `merge_sort(arr, 0, arr.length-1)`

# 答案2

``````merge_sort(first_array);
merge_sort(second_array);
``````

``````first_array = merge_sort(first_array);
second_array = merge_sort(second_array);
``````

``````int[] sorted_first_array = merge_sort(first_array);
int[] sorted_second_array = merge_sort(second_array);
// 然后合并
int[] sorted_array = merge(sorted_first_array, sorted_second_array);
// 然后返回
return sorted_array;
``````

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.

• 本文由 发表于 2020年7月28日 17:28:12
• 转载请务必保留本文链接：https://go.coder-hub.com/63131039.html
• algorithm
• arrays
• java
• mergesort
• sorting

go 42

go 38

go 41

go 59