例24：归并排序

在之前算法考试之前看过归并排序，当时觉得好难啊，卧槽怎么会有这么难的排序算法啊什么的。但是如今再一看其实略一眼就明白了，其原理非常简单，就是通过分成两个已排序的数组合并到一块而已，合并的时候也没有什么特别的技巧，也就是一个个比较而已额。其步骤大概是（个人算法的步骤，还有其他的如多路归并排序或者细节有些不同，但我个人是这样写的）：

1.将给定数组递归不断的分成两半，直到数组元素只有一个为止。

2.认为一个元素的数组是已排序的数组，此时数组已不能再分，开始合并。

3.两个数组合并时，元素由前到后有序一一进行比较，大者不动，小者添加到新的数组中并使数组遍历的下标i加一，直到两者其中一者元素遍历完成为止。

4.由于合并的两个数组都是有序的，将俩者中未完成的一组直接按顺序添加到新数组中，将新数组赋入原数组中，结束此轮递归进入上一轮，直到最初的递归函数为止，排序结束。

代码如下：

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

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

void MergeSort(int a[],int first,int last,int temp[])
{
     if(first < last)
     {
              int mid = (first + last)/2;
              MergeSort(a,first,mid,temp);
              MergeSort(a,mid+1,last,temp);
              MergeArraySort(a,first,mid,last,temp);
     }
}
int main()
{
    int pArray[20],nCount,tempArray[20];
    while(~scanf("%d",&nCount) && nCount)
    {
                               for(int i = 0;i<nCount;i++)
                               {
                                       scanf("%d",&pArray[i]);
                               }
                               MergeSort(pArray,0,nCount-1,tempArray);
                               for(int i = 0;i<nCount;i++)
                               {
                                       printf("%d ",pArray[i]);
                               }
                               printf("
");
    }
    
    return 0;
}