归并排序（看了别人的博客明白了也写个博客，希望这样不算抄袭~）

归并排序还是用到了递归（原来难理解的东西是因为递归），所以先不说递归就不会觉得难了。（额、、可惜已经说了，好吧，先当我没说= =）

  那么先讨论一个问题：怎么把两个有序的数组合并成一个新的有序数组？

答：这个非常简单，只要从比较二个数列的第一个数，谁小就先取谁，取了后就在对应数列中删除这个数。然后再进行比较，如果有数列为空，那直接将另一个数列的数据依次取出即可。

（此答摘自我看懂的那个人的博客，为防止侵权这里贴上他的网址：http://blog.csdn.net/morewindows/article/details/6678165/）

那么知道怎么合并两个数组了，完全可以写一个函数实现合并一个数组的功能：

  void mergearray(int *a,int left,int mid,int right,int *temp)

这个函数的功能是把a[left]~a[mid] 和a[mid+1]~a[right]这两个“数组”合并成一个数组，然后再取代原先这一块a数组的位置。其中temp这个临时空间是很有必要的。

代码如下：

void mergearray(int *a,int left,int mid,int right,int *temp)
{
    int i,j,m,n,k;
    i=left;
    j=mid+1;
    m=mid;
    n=right;
    k=0;
    while (i<=m&&j<=n){
        if (a[i]<a[j]){
            k++;
            temp[k]=a[i];
            i++;
        }
        else{
            k++;
            temp[k]=a[j];
            j++;            
        }
    }
    while (i<=m){
        k++;
        temp[k]=a[i];
        i++;
    }
    while (j<=n){
        k++;
        temp[k]=a[j];
        j++;
    }
    for (i=1;i<=k;i++){
        a[left+i-1]=temp[i];
    }
}

好了，现在我们已经知道怎么合并有序了，重点要来了。怎么把数组变得有序呢？因为我们知道，要合并有序，前提先得有序啊！

答案我想你已经猜到了——递归。

我们不妨写一个函数来实现归并排序的功能 void mergesort(int *a,int left,int right,int *temp)

如果你看了我汉诺塔的那篇博客，现在应该会习惯我这样来说——

    要想让一个数组有序void mergesort(int *a,int left,int right,int *temp)，分为如下步骤：

    第一步：让数组的前一半有序　　void mergesort(a,left,mid,temp);

    第二步：让数组的后一半有序　　void mergesort(a,mid+1,right,temp);

    第三步：合并两个有序的数组生成新的有序　　void mergearray(a,left,mid,right,temp).

这样就完成了。是不是恍然大悟了呢~如果是，可以参考下面的C语言代码：

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

void mergearray(int *a,int left,int mid,int right,int *temp)
{
    int i,j,m,n,k;
    i=left;
    j=mid+1;
    m=mid;
    n=right;
    k=0;
    while (i<=m&&j<=n){
        if (a[i]<a[j]){
            k++;
            temp[k]=a[i];
            i++;
        }
        else{
            k++;
            temp[k]=a[j];
            j++;            
        }
    }
    while (i<=m){
        k++;
        temp[k]=a[i];
        i++;
    }
    while (j<=n){
        k++;
        temp[k]=a[j];
        j++;
    }
    for (i=1;i<=k;i++){
        a[left+i-1]=temp[i];
    }
}

void mergesort(int *a,int left,int right,int *temp)
{
    if (left<right) {
        int mid=(left+right)/2;
        mergesort(a,left,mid,temp);
        mergesort(a,mid+1,right,temp);
        mergearray(a,left,mid,right,temp);
    }
}

int main()
{
    int n;
    scanf("%d",&n);
    int *a=malloc(n*sizeof(int));
    int *p=malloc(n*sizeof(int));
    int i;
    for (i=1;i<=n;i++){
        scanf("%d",a+i);
    }
    mergesort(a,1,n,p);
    for (i=1;i<=n;i++){
        printf("%d:%d
",i,a[i]);
    }
    free(a);
    free(p);
    return 0;
}