#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
void  wrt(int key[], int sz);
void  mergesort(int key[], int n);
void  merge(int a[], int b[], int c[], int m, int n);


void merge(int a[],int b[],int c[], int m,int n)
{
    int i=0,j=0,k=0;
    while(i<m && j<n)
        if(a[i] < b[i])
            c[k++]=a[i++];
        else
            c[k++]=b[j++];
        while (i<m)
            c[k++]=a[i++];
        while (j<n)
            c[k++] = b[j++];
}
void mergesort(int key[],int n)
{
    int j,k,m,*w;
    for(m = 1; m < n; m *= 2)
        ;
    if (n < m)
    {
        printf("ERROR:Array size not apower of 2 - bye!\n");
        exit(1);
    }
    w = calloc(n, sizeof(int));
    assert(w != NULL);
    for (k = 1; k < n; k *=2)
    {
        for(j = 0; j < n - k; j += 2*k)
            merge(key + j, key + j + k, w + j, k, k);

        for (j = 0; j < n; ++j)
            key[j] = w[j];
    }



    free(w);
}


void wrt(int key[], int sz)
{
    int  i;
    for (i = 0; i <sz; ++i)
        printf("%4d%s",key[i],((i < sz - 1) ? "" : "\n"));
}
int main(void)
{
    int sz,key[]={ 4, 3, 6, 67,5,8,7,9};
    sz=sizeof(key) / sizeof(int);
    printf("Before mergesort:\n");
    wrt(key,sz);
    mergesort(key,sz);
    printf("After mergesort:\n");
    wrt(key,sz);
    return 0;
}

调试看看

调试结果不对啊

应该是从小到大排列的

if (n < m)
{
    printf("ERROR:Array size not apower of 2 - bye!\n");
    exit(1);
}
w = calloc(n, sizeof(int));
assert(w != NULL);
//for (k = 1; k < n; k *=2)
for (k = n/2; k >= 1; k /=2)    //这样改就好了
{
    for(j = 0; j < n - k; j += 2*k)
        merge(key + j, key + j + k, w + j, k, k);

    for (j = 0; j < n; ++j)
        key[j] = w[j];
}

但是把数字增加到16 个就又不行了。不知道哪的问题

算法思路是什么？？

希望以后你能将程序的作用说明一下，这样便于理解程序，最好加入注释。
 w = calloc(n, sizeof(int));这里应该这样写：w=(int *)calloc(n,sizeof(int));
 printf("%4d%s",key[i],((i < sz - 1) ? "" : "\n"));应该把%s换为%c,? "" :这里的两个 "" 中间应该有空格，反正在我的编译器上，如果没有空格的话会有警告的。
你的编程思路有点看不懂，对数组的排序不用这么复杂吧，有简单地算法的。比如冒泡排序，直接排序等，很多的。

话说，楼主的程序是递归程序吗？我左看右看没看出在哪递归的啊……
递归定义：程序调用自身的编程技巧称为递归（ recursion），一个过程或函数在其定义或说明中有直接或间接调用自身的一种方法。（引自百度）
还是我孤陋寡闻，这是排序的一种方法就是叫递归排序？……

我在书上整下来的，运行后结果错误，不知道原因在哪里