我从 CLRS 完成的合并排序代码有什么问题？

Question

输出错误！我已经尝试了每一个条件，但未能得到真正的结果

I tried to accomplish this from the clrs book pseudo-code but I failed. I am trying to write merge sort using iterators to implement myself pseudo-code in c language, but for some reason, this code is compiling but the outcome is not sorted. Can someone figure out what is wrong with it? it seems perfectly fine to my untrained eyes.

#include <stdio.h>
#include<math.h>
#include <stdlib.h>

int a[] = {5,3,65,6,7,3,7,8};

void print_array(int a[], int size)
{
    int i;
    for(i = 0;i < size;i++)
    {
        printf("%d ",a[i]);
    }
}
void merge(int a[],int p,int q,int r)
{
    int n1,n2,i,j,k;
    n1 = q - p + 1;
    n2 = r - q;
    int l[n1];
    int m[n2];
    for(i = 0; i < n1; i++)
        l[i] = a[i+p];
    for(j = 0; j < n2; j++)
        m[j] = a[q+1+j];
    l[n1] = 9999999;
    m[n2] = 9999999;
    i = 0;
    j = 0;
    for(k = p;k < r; k++)
    {
        if(l[i] <= m[j])
        {
            a[k] = l[i];
            i = i+1;
        }
        else
        {
            a[k] = m[j];
            j = j+1;
        }
    }
}
void merge_sort(int a[],int p,int r)
{
    if(p < r)
    {
        int q = floor((p + r) / 2);
        merge_sort(a,p,q);
        merge_sort(a,q+1,r);
        merge(a,p,q,r);
    }
}
int main()
{
    int size = (sizeof(a) / sizeof(a[0]));
    print_array(a,size);
    printf("\n");
    merge_sort(a,0,size);
    print_array(a,size);
    return 0;
}

//for this input out put is showing
//-1 -1 3 3 3 -1 6 7

Answer 1

请注意数组边界和大小：

你的参数r不是数组的大小，而是最右边元素的索引，所以你应该调用merge_sort(a, 0, size - 1);.
当你想使用一个大的sentinel值时，实际数组之后，你必须为其分配space，所以：
```
int l[n1];
int m[n2];
```
因为你的值r是最后一个元素的index，合并的时候一定要考虑，你的循环条件应该是for(k = p; k <= r; k++).
（不是真正的问题，但是您不需要像 JavaScript 那样使用 floor。当 a 和 b 是整数，a / b 将执行结果为整数的除法。）

在 C 中，数组（和一般范围）具有包含下限和排除上限：lo 是第一个有效索引，hi 是有效范围后的第一个无效索引。对于数组索引，lo 和 hi 为零，数组大小。

接受这个约定。 C 索引导致以下样式：

范围的长度是 hi - lo;
正向循环是 for (i = lo; i < hi; i++)；
相邻范围共享 hi 和 lo 值。

例如，在您的 merge 函数中，中间值 p 将是右侧范围中的第一个值，也是左侧范围的唯一上限。

如果伪代码或其他语言的代码使用从一开始的索引，我建议将其翻译成从零开始的、独占的 C 的上限样式。一段时间后，你会怀疑是假的 - 1 和 <=。 :)

我从 CLRS 完成的合并排序代码有什么问题？

What's wrong with this merge sort code I have done from the CLRS?

c

sorting

merge

clrs