问题

尝试在Java中实现归并排序。我在脑海中反复检查了我的代码，觉得它应该是可以工作的，但显然我做错了些什么。以下是代码部分：

```java
    public static void mergeSort(int[] input, int start, int end) {
        if (end - start < 2)
            return;
        
        int mid = (start + end) / 2;
        mergeSort(input, start, mid);
        mergeSort(input, mid + 1, end);
        merge(input, start, mid, end);
    }

    public static void merge(int[] input, int start, int mid, int end) {
        if (input[mid - 1] <= input[mid])
            return;
         
        int i = start;
        int j = mid;
        int tempIndex = 0;
        int[] temp = new int[end - start]; //合并两个数组的大小
        
        /* 如果 i >= mid，意味着数组的左部分已经排序完成，
           反之如果 j >= end，那么右部分也是一样的。
           一旦发生这种情况，我们可以将剩余的元素直接复制到临时数组中。
        */
        while (i < mid && j < end) {
            temp[tempIndex++] = (input[i] <= input[j]) ? input[i++] : input[j++];
        }
        
        // 复制左部分中剩余的元素
        while (i < mid)
            temp[tempIndex++] = input[i++];
        
        // 复制右部分中剩余的元素
        while (j < end)
            temp[tempIndex++] = input[j++];
        
        // 将排序后的临时数组复制回原数组
        // 这是我认为可能出错的地方
        for (int k = 0; k < temp.length; k++) {
            input[start + k] = temp[k];    
        }
     }

我认为问题可能出在没有正确地将临时数组中的排序元素复制回原始数组，但我不太确定。我在代码中加了注释来解释我的逻辑。

<details>
<summary>英文:</summary>
Trying to implement merge sort in Java. I&#39;ve gone over my code a bunch in my head and I feel like it should be working, but obviously I&#39;m doing something wrong. Heres the code

public static void mergeSort(int[] input, int start, int end) {
if (end - start < 2)
return;
int mid = (start + end) / 2;
mergeSort(input, start, mid);
mergeSort(input, mid + 1, end);
merge(input, start, mid, end);
}
public static void merge(int[] input, int start, int mid, int end) {
if (input[mid - 1] <= input[mid])
return;
int i = start;
int j = mid;
int tempIndex = 0;
int[] temp = new int[end - start]; //combined size of both arrays being merged
/*if i is >= mid, then that means the left portion of the array is done being sorted
and vice versa if j >= end. Once this happens, we should be able to
just copy the remaining elements into the temp array 
*/
while (i < mid && j < end) {
temp[tempIndex++] = (input[i] <= input[j]) ? input[i++] : input[j++];
}
//Copying left over elements in left portion
while (i < mid)
temp[tempIndex++] = input[i++];
//Copying left over elements in right portion
while (j < end)
temp[tempIndex++] = input[j++];
//Copy the sorted temp array into the original array
//This is where I think I must be messing up
for (int k = 0; k < temp.length; k++) {
input[start + k] = temp[k];    
}
}

I think it must be that im not copying correctly the temp array with the sorted elements back into the original array, but I'm not sure. I wrote comments on my code explaining my logic. 
</details>
# 答案1
**得分**: 2
看一下以下的变更：
1. 计算中间值
&gt; int mid = start + (end - start) / 2;
2. 正确地分配指针 i 和 j。
&gt; int i = start;
&gt; int j = mid+1;
3. 正确的临时数组大小。
&gt; int [] temp = new int[end-start+1];
4. 修正了代码中的 while 循环条件。
class Solution{
public static void mergeSort(int[] input, int start, int end) 
{
if (end == start ) return;
int mid = start + (end - start) / 2;
mergeSort(input, start, mid);
mergeSort(input, mid+1, end);
merge(input, start, mid, end);
}
public static void merge(int[] input, int start, int mid, int end) {
// 下面这个指令是不必要的
// if(input[mid-1] &lt;= input[mid]) return;
int i = start;
int j = mid+1;
int tempIndex = 0;
int [] temp = new int[end-start+1]; // 被合并的两个数组的总大小
/* 如果 i &gt;= mid，则意味着数组的左部分已经排序完成，反之亦然，如果 j &gt;= end，则意味着数组的右部分已经排序完成。一旦发生这种情况，我们应该能够将剩余的元素直接复制到临时数组中 */
while(i &lt;= mid &amp;&amp; j &lt;= end){
temp[tempIndex++] = (input[i] &lt;= input[j]) ? input[i++] : input[j++];
}
// 复制左部分中剩余的元素
while(i &lt;= mid)
temp[tempIndex++] = input[i++];
// 复制右部分中剩余的元素
while(j &lt;= end)
temp[tempIndex++] = input[j++];
// 将排序好的临时数组复制到原始数组中
// 这是我认为我可能搞错的地方
for(int k = 0; k &lt; temp.length; k++){
input[start+k] = temp[k];    
}
}
public static void main(String[] args){
int[] input = {9,4,6,8,5,7,0,2};
mergeSort(input,0,7);
for(int i : input)
System.out.println(i);    
}
}
<details>
<summary>英文:</summary>
Take a look at the following changes:
1. Calculating mid
&gt; int mid = start + (end - start) / 2;
2. Assigning pointers i,j correctly.
&gt; int i = start;
&gt; int j = mid+1;
3. Correct size of temp array.
&gt; int [] temp = new int[end-start+1];
4. Corrected while loops condition in the code.
class Solution{
public static void mergeSort(int[] input, int start, int end) 
{
if (end == start ) return;
int mid = start + (end - start) / 2;
mergeSort(input, start, mid);
mergeSort(input, mid+1, end);
merge(input, start, mid, end);
}
public static void merge(int[] input, int start, int mid, int end) {
// No Need of the under mentioned instruction
// if(input[mid-1] &lt;= input[mid]) return;
int i = start;
int j = mid+1;
int tempIndex = 0;
int [] temp = new int[end-start+1]; //combined size of both arrays being merged
/*if i is &gt;= mid, then that means the left portion of the array is done being sorted and vice versa if j &gt;= end. Once this happens, we should be able to just copy the remaining elements into the temp array */
while(i &lt;= mid &amp;&amp; j &lt;= end){
temp[tempIndex++] = (input[i] &lt;= input[j]) ? input[i++] : input[j++];
}
//Copying left over elements in left portion
while(i &lt;= mid)
temp[tempIndex++] = input[i++];
//Copying left over elements in right portion
while(j &lt;= end)
temp[tempIndex++] = input[j++];
//Copy the sorted temp array into the original array
//This is where I think I must be messing up
for(int k = 0; k &lt; temp.length; k++){
input[start+k] = temp[k];    
}
}
public static void main(String[] args){
int[] input = {9,4,6,8,5,7,0,2};
mergeSort(input,0,7);
for(int i : input)
System.out.println(i);    
}
}
</details>