我的归并排序代码有什么问题?

Question

只是写一些基本的合并排序代码，我不知道我的逻辑是否有问题。对我来说应该没问题。

所以，理想情况下，它应该按顺序打印出元素:1 2 8 11 17 19 25 50。

但是显示结果是:8 2 11 1 17 19 25 50

我不明白这段代码有什么问题。我的逻辑有问题吗?

如果有人能帮我，那就太好了。如果这是一个非常愚蠢的问题，我很抱歉。

public class MergeSort
{
static final int arr[] = {8, 2, 19, 25, 11, 1, 17, 50};
static int sorted[] = new int[arr.length];
public static void main(String args[])
{
mergeSort(0, arr.length - 1);

display();
}

static void display()
{
for(int i=0; i<sorted.length; i++)
{
System.out.print(sorted[i] + " ");
}
}

static void mergeSort(int first, int last)
{
if(first < last)
{
int mid = (first + last)/2;
mergeSort(first, mid);
mergeSort(mid + 1, last);
merge(first, mid, last);
}
}

static void merge(int first, int mid, int last)
{
int ansIndex = 0;
int index1 = first;
int index2 = mid + 1;

while(index1 <= mid && index2 <= last)
if(arr[index1] < arr[index2])
{
sorted[ansIndex] = arr[index1];
index1++;
ansIndex++;
}
else if(arr[index2] < arr[index1])
{
sorted[ansIndex] = arr[index2];
index2++;
ansIndex++;
}
else
{
sorted[ansIndex] = arr[index1];
index1++; index2++; ansIndex++;
}

if(index1 <= mid)
while(index1 <= mid)
{
sorted[ansIndex] = arr[index1];
ansIndex++; index1++;
}
else if(index2 <= last)
while(index2 <= last)
{
sorted[ansIndex] = arr[index2];
index2++; ansIndex++;
}
}
}

Answer 1

您的错误是在每一步都使用相同的数组arr和sorted而不复制数据。

最简单的校正是将sorted的范围0..ansIndex复制到merge末尾的arr的范围first..last

display也应该显示arr(sorted只是临时缓冲区)