合并排序，合并期间重新排列数组.爪哇岛

Question

我在合并排序的数组中遇到了一些问题。我遇到的每种情况，合并都可以正常工作，直到它命中递归方法并将先前合并的数组发回。在大多数情况下，它会重新排列已经排序的数组并弄乱第二个合并方法。例如：(3((2((1((4( -> (2,3((1,4( -> (1,3,2,4( 将是一个可能的结果。我做错了什么可能导致这种情况？

public static int[] mergeSort(int[] numbers) {
if (numbers.length == 1) {
return numbers; }
int[] leftSide = new int[numbers.length/2];
int[] rightSide = new int[numbers.length-leftSide.length];
System.arraycopy(numbers,0,leftSide,0,leftSide.length);
System.arraycopy(numbers,leftSide.length,rightSide,0,rightSide.length);
mergeSort(leftSide);
mergeSort(rightSide);
displayArray(leftSide);
displayArray(rightSide);
numbers = merge(leftSide,rightSide);
System.out.println("=============");
return numbers;
}  
public static int[] merge(int[] left, int[] right) {
int[] temp = new int[left.length+right.length];
int l = 0;
int r = 0;
int t = 0;
while (l < left.length && r < right.length) {
if (left[l] > right[r]) {
temp[t] = right[r];
r++;
t++; }
else {
temp[t] = left[l];
l++; 
t++; }
}//while
while (l < left.length) {
temp[t] = left[l];
l++;
t++; }
while (r < right.length) {
temp[t] = right[r];
r++; 
t++; }
displayArray(temp);
return temp;
}

Answer 1

mergeSort 函数返回一个排序数组，我们不跟踪该数组。由于排序数组(左和右(丢失，合并函数再次拾取未排序的左右数组。解决方法是更新

mergeSort(leftSide);
mergeSort(rightSide);

自

leftSide = mergeSort(leftSide);
rightSide = mergeSort(rightSide);

这会将它们更新为各自的排序值