代码：
#include <stdio.h>
#include <stdlib.h>
void merge(int number[],int first,int last,int mid)
{
   
}
void merge_sort(int number[],int first,int last)
{
    int mid=0;
    if(first<last)
    {
    mid=(first+last)/2;
    merge_sort(number,first,mid);
    merge_sort(number,mid+1,last);
    merge(number,first,last,mid);
    }
}
int main()
{
    int number[10]={0},n,i;
    scanf("%d",&n);
    for(i=0;i<n;i++)
    scanf("%d",&number[i]);
    merge_sort(number,0,n-1);
    for(i=0;i<n;i++)
    printf("%d ",number[i]);
    system("pause");
    return 0;
}



写到merge这个函数就感觉写不下去了。请教各位高手，这个函数怎么写？

学习 数据结构 得选用 正规教材，  网上那些不入流的代码还是少参考为好。/

void merge(int a[], int left, int m, int right)
{
    int aux[MAX_NUM] = {0};
    int i, j, k;
   
    for (i = left, j = m+1, k = 0; k <= right-left; k++)
    {
         if (i == m+1)
         {
            aux[k] = a[j++];
            continue;
         }
        
         if (j == right+1)
         {
             aux[k] = a[i++];
             continue;
         }
  
         if (a[i] < a[j])
         {
             aux[k] = a[i++];
         }
         else
         {
             aux[k] = a[j++];
         }
    }

    for (i = left, j = 0; i <= right; i++, j++)
    {
        a[i] = aux[j];
    }
}

归并排序需要 额外的 辅助空间， 代码 aux就是起这个作用的， 先排好序， 再刷回原数组。

自从 用过Astyle， 代码写的越发的 规范了。

[ 本帖最后由 BlueGuy 于 2011-1-27 16:40 编辑 ]

写好了，这个代码我看不懂，能不能解释一下？
#include <stdio.h>
#include <stdlib.h>
void merge(int number[],int first,int last,int mid)
{
    int number_temp[10]={0};
    int i=first,j=mid+1,k;
    for(k=0;k<=last-first;k++)
    {
    if (i==mid+1)
    {
    number_temp[k]=number[j++];
    continue;
    }
    if (j==last+1)
    {
    number_temp[k]=number[i++];
    continue;
    }
    if (number[i]<number[j])  number_temp[k]=number[i++];
    else  number_temp[k]=number[j++];
    }
    for (i=first,j=0;i<=last;i++,j++)
    number[i] = number_temp[j];
}
void merge_sort(int number[],int first,int last)
{
    int mid=0;
    if(first<last)
    {
    mid=(first+last)/2;
    merge_sort(number,first,mid);
    merge_sort(number,mid+1,last);
    merge(number,first,last,mid);
    }
}
int main()
{
    int number[10]={0},n,i;
    scanf("%d",&n);
    for(i=0;i<n;i++)
    scanf("%d",&number[i]);
    merge_sort(number,0,n-1);
    for(i=0;i<n;i++)
    printf("%d ",number[i]);
    system("pause");
    return 0;
}

归并排序 作为用递归实现的 分治算法，显然是将一个数组 对半分为两个数组，并且这两个数组是 有序的。
那么 排序的 核心就是 将两个 有序的数组 合并 为 一个有序的数组。

变量 mid将数组分为两部分，
a[left]...a[mid]
a[mid+1]...a[right]
数组的元数个数为 right-left+1.
合并过程中，如果其中一个数组元素已经合并完，（条件是 i == m+1) || j == right+1,  这个应该很容易看明白，
因为 数组索引已经移动到 数组的尾部了） 就将另一个数组的余下元素，直接复制到 辅助数组中...

有非递归不用，就用递归
思想上书有说，就不说，我想说就是怎样使用
设a1,a2是己经排序好的
a1 = a2  a2复制到a1（其它也行，随你定义）
最后要知道它们（这里指a1,a2）头尾位置在那里，与归并函数进行接口就行

归并排序的 非递归写法难度有点大，而且比较丑陋，
估计 只有为数不多的同学能够 徒手打出来归并排序，

楼上如果牛叉， 不妨试一试， 菜鸟观望。

非递归的不像你想像丑陋，实现算法书上有。

能逐句解释吗？

//合并排序
void merge(int a[], int left, int m, int right)
{
    int aux[MAX_NUM] = {0};  // 临时数组 （若不使用临时数组，将两个有序数组合并为一个有序数组比较麻烦）
    int i; //第一个数组索引
    int j; //第二个数组索引
    int k; //临时数组索引
   
   
    for (i = left, j = m+1, k = 0; k <= right-left; k++) // 分别将 i, j, k 指向各自数组的首部。
    {
         //若 i 到达第一个数组的尾部，将第二个数组余下元素复制到 临时数组中
         if (i == m+1)
         {
            aux[k] = a[j++];
            continue;
         }   
      
         //若 j 到达第二个数组的尾部，将第一个数组余下元素复制到 临时数组中
         if (j == right+1)
         {
             aux[k] = a[i++];
             continue;
         }
         
         //如果第一个数组的当前元素 比 第二个数组的当前元素小，将 第一个数组的当前元素复制到 临时数组中
         if (a[i] < a[j])
         {
             aux[k] = a[i++];
         }
         //如果第二个数组的当前元素 比 第一个数组的当前元素小，将 第二个数组的当前元素复制到 临时数组中
         else
         {
             aux[k] = a[j++];
         }
    }
   
    //将有序的临时数组 元素 刷回 被排序的数组 a 中，
    //i = left , 被排序的数组a 的起始位置
    //j = 0， 临时数组的起始位置
    for (i = left, j = 0; i <= right; i++, j++)
    {
        a[i] = aux[j];
    }
}

我写代码从不写注释的，觉得自己写的代码比注释还注释，
看样子菜鸟我 自以为是 了