我的合并排序没有给出正确的排序数组，任何人都可以解释一下吗?

Question

我正在努力理解和实现这个算法几个小时，我很确定，我正在按照标准算法做所有事情，但它仍然不起作用。 我正在关注一本名为"Thomas H cormen的算法导论"的书。

#include<iostream>
using namespace std;
//function to divide the array until it has only one element
void merge_sort(int[], int, int);
// function to merge two sorted arrays
void merge(int[], int, int, int);
// global array - to write the final sorted array in this
int na[100];
void main() {
int a[50]; //input array
cout << "Enter an unsorted array of 10 elements" << endl;
for (int i = 0; i < 10; i++) {
cin >> a[i];
}
merge_sort(a, 0, 9);  // calling merge_sort
for (int i = 0; i < 10; i++) {
//print final array
cout << na[i] << endl;
}
}
void merge_sort(int a[], int p, int r) {
// p is 0 , r is final bound
if (p < r) {
int q;
q = (p + r) / 2; //finding middle element
merge_sort(a, p, q);
merge_sort(a, q + 1, r);
merge(a, p, q, r);
}
}
// for two sorted sub-array from p to q and from q+1 to r, this function 
// will compare first element of each sub-array and will place the smaller 
// one in final array until every element is sub-array is in final sorted 
//array
void merge(int a[], int p, int q, int r) {
int n1 = q - p + 1;
int n2 = r - q;
int l[50];
int ri[50];
for (int i = 0; i < n1; i++) {
l[i] = a[p + i ];
}
l[n1] = 99999;
for (int j = 0; j < n1; j++) {
ri[j] = a[q + j + 1];
}
ri[n2] = 99999;
int i = 0;
int j = 0;
for (int k = p; k <= r; k++) {
if (l[i] <= ri[j]) {
na[k] = l[i];
i = i + 1;
}
else {
na[k] = ri[j];
j = j + 1;
}
}
}

Answer 1

您使用a中的值进行合并，但您将排序的子数组放在na中。如果子数组已排序，则merge操作只会为您提供已排序的数组。正如 BLUEPIXY 所建议的那样，您需要使用一个容器来存储排序的子数组和合并排序的子数组：无论您为此目的使用a还是na并不重要，但a会是更好的选择，因为您已经拥有它。

Answer 2

1. 尝试阅读在 StackOverflow 上提问的指南。

2. 在 mergeSort 中，您正在合并未排序的数组而不是排序的数组(void merge_sort(int a[], int p, int r)：由于您要合并a[]，您应该对a[]而不是na[]进行排序)。

否则，合并na[]段并将其复制到a[]的每个函数调用中对 merge_sort(:);