我已尝试实施合并排序，但无法找到我的代码的确切问题。该程序没有显示错误，但我没有得到所需的输出

Question

尝试实现归并排序，下面是代码。让我知道是否有任何问题。我的合并功能有什么错误吗？无法指出我的代码中的确切问题。任何有关相同的帮助将不胜感激。

#include <iostream>
using namespace std;

合并两个排序数组的合并函数

void merge(int arr[], int start, int mid, int end) {
    int n1 = mid - start + 1;
    int n2 = end - mid;
    
    int arr1[n1], arr2[n2];
    for (int i = 0; i < n1; i++) {
        arr1[i] = arr[start + i];
    }
    for (int j = 0; j < n2; j++) {
        arr2[j] = arr[mid + 1 + j];
    }

    int i;
    int j;
    int p;
    i = 0;
    j = 0;
    p = start;
    
    while (i < n1 && j < n2) {
        if (arr1[i] <= arr2[j]) {
            arr[p] = arr1[i];
            i++;
        } else {
            arr[p] = arr2[j];
            j++;
        }
        p++;
    }
    while (i < n1) {
        arr[p] = arr1[i];
        i++;
        p++;
    }

    while (j < n2) {
        arr[p] = arr2[j];
        i++;
        p++;
    }
}

递归调用合并排序

void merge_sort(int arr[], int start, int end) {
    if (start >= end) {
      return;
    }
    if (start < end) {
        int mid = start + (end - 1) / 2;
        merge_sort(arr, start, mid);
        merge_sort(arr, mid + 1, end);
        merge(arr, start, mid, end);
    }
}

打印数组的打印函数

void printArray(int arr[], int size) {
    for (int i = 0; i < size; i++)
        cout << arr[i] << " ";
    cout << endl;
}

主要功能

int main() {
    int arr[] = { 6, 5, 12, 10, 9, 1 };
    int n = sizeof(arr) / sizeof(arr[0]);
    
    merge_sort(arr, 0, n - 1);
    cout << "The sorted array is: " << endl;
    printArray(arr, n);
}

Answer 1

代码有 2 个错误：

将中点计算为 int mid = start + (end - 1) / 2; 是不正确的。你应该改为写：
```
  int mid = start + (end - start) / 2;
```
在 merge 的最后一个循环中，您递增 i 而不是 j。请注意，此循环是多余的，因为 arr2 的剩余元素已经在 arr.
的末尾

您遵循合并排序实现中的经典约定，其中 end 是切片中最后一个元素的索引。这个约定需要多次+1 / -1调整，容易出错

在数组索引从 0 开始的 C 和相关语言中，使用不同的约定更为惯用：传递 start 作为切片第一个元素的索引，并且 end 作为刚好超过最后一个元素的索引。这允许指定空拼接并生成更清晰的代码。

这是修改后的版本：

#include <iostream>

using namespace std;

// Merge function to merge the two sorted arrays
void merge(int arr[], int start, int mid, int end) {
    int n1 = mid - start;
    int n2 = end - mid;
    int arr1[n1], arr2[n2];

    for (int i = 0; i < n1; i++) {
        arr1[i] = arr[start + i];
    }
    for (int j = 0; j < n2; j++) {
        arr2[j] = arr[mid + j];
    }

    int i = 0;
    int j = 0;
    int p = start;
    
    while (i < n1 && j < n2) {
        if (arr1[i] <= arr2[j]) {
            arr[p] = arr1[i];
            i++;
        } else {
            arr[p] = arr2[j];
            j++;
        }
        p++;
    }
    while (i < n1) {
        arr[p] = arr1[i];
        i++;
        p++;
    }
    // the remaining elements from `arr2` are already in place in `arr`
}

// Calling mergesort recursively
void merge_sort(int arr[], int start, int end) {
    if (end - start > 1) {
        int mid = start + (end - start) / 2;
        merge_sort(arr, start, mid);
        merge_sort(arr, mid, end);
        merge(arr, start, mid, end);
    }
}

// Print function to print the array
void printArray(const int arr[], int size) {
    for (int i = 0; i < size; i++)
        cout << arr[i] << " ";
    cout << endl;
}

// Main function
int main() {
    int arr[] = { 6, 5, 12, 10, 9, 1 };
    int n = sizeof(arr) / sizeof(arr[0]);
    
    merge_sort(arr, 0, n);
    cout << "The sorted array is: " << endl;
    printArray(arr, n);
    return 0;
}

我已尝试实施合并排序，但无法找到我的代码的确切问题。该程序没有显示错误，但我没有得到所需的输出

I have tried to implement mergesort and am unable to find the exact problem of my code. The program shows no errors but I do not get a desired output

c++

recursion

mergesort