合并排序：需要从临时数组复制元素

Question

我一直在试着分析mergesort，但我被一个奇怪的错误击中了。这是我的代码：

int merge(int *a,int st,int mid,int en)
{
    int i,j,l,m;
    i = st;
    l = st;
    m = mid + 1;
    while((l<=mid) && (m <= en))
    {
        if(a[l] <= a[m])
        {
            temp[i] = a[l];
            l++;
            i++;
        }
        else
        {
            temp[i] = a[m];
            m++;
            i++;
        }
    }
    if(l <= mid)
    {
        for(j=l;j<=mid;j++)
        {
            temp[i] = a[j];
            i++;
        }
    }
    else 
    {
        for(j=m;j<=en;j++)
        {
            temp[i] = a[j];
            i++;
        }
    }
    for(j=st;j<=en;j++) // ??
        a[j] = temp[j];  // ??
}

void mergesort(int *a,int st,int en)
{
    int mid;
    if(st<en)
    {
        mid = (st+en)/2;
        mergesort(a,st,mid);
        mergesort(a,mid+1,en);
        merge(a,st,mid,en);
    }
}

int main()
{
    int i,n;
    scanf("%d",&n);
    for(i=0;i<n;i++)
        scanf("%d",&a[i]);
    mergesort(a,0,n-1);
    for(i=0;i<n;i++)
        printf("%d\n",temp[i]);
    getch();
    return 0;
}

我一直在使用典型的合并排序代码。我在理解为什么需要将内容从临时数组复制到主数组以获得正确的输出时遇到了问题。我尝试了以下输入：5（术语数量），
4 2

我得到的输出为：3 2 4 4 5，而没有将内容从临时数组复制到主数组，如果我使用“注释”循环进行复制，输出很好，即2 3 4 4 5。我只是不明白，为什么会这样？

Answer 1

复制是必要的，因为复制是在合并函数中完成的，而不是在合并函数中完成的。合并函数必须递归地一次又一次调用；所以临时数组会继续变化。

在每次mergesort调用中，需要将原始数组中部分排序的部分放入原始数组中。部分排序的部分实际上是临时数组。