归并排序，顾名思义-先递归再合并的排序方式，一层一层的递归，当递归到最底层的时候，进行合并操作，这也是分治算法的经典运用。

首先是要进行把两个有序的序列进行合并操作，需要借助辅助空间，先把有序序列存储在辅助空间中，在从辅助空间把有序序列复制到原序列中，完成合并操作，相应代码如下：

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

然后就是递归函数的操作，先把原来序列分成两组无序序列，再分别把这两组无序序列分别分为两个无序序列，直到不能再分为止，默认单个元素为有序序列，然后进行合并排序，相应代码如下：

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) ;        Merge(a,first,mid,last,temp) ;    }}

 

全部归并排序算法代码实现如下：

#include
     
      void Merge(int a[] , int first , int mid , int last , int temp[])   {    int i = first , j = mid + 1 , k = 0 ;    while(i <= mid && j <= last)        if(a[i] < a[j])            temp[k++] = a[i++] ;        else            temp[k++] = a[j++] ;        while(i <= mid)            temp[k++] = a[i++] ;        while(j <= last)            temp[k++] = a[j++] ;        for(i = 0 ; i < k ; i++)            a[first+i] = temp[i] ;}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) ;        Merge(a,first,mid,last,temp) ;    }}int main()  {    int n ;    scanf("%d",&n) ;    int a[100] , i;    for(i = 0 ; i < n ; i++)        scanf("%d",&a[i]) ;    int *temp = new int[n] ;    Mergesort(a,0,n-1,temp) ;    delete[] temp ;    for(i = 0 ; i < n ; i++)        printf("%d ",a[i]) ;    printf("\n") ;    return 0 ;}
     

归并排序算法的效率还是比较高的，设数列长度为n，则将数列分为小数列一共需要logN步，每步都是合并有序数列的过程，所以归并排序的时间复杂度为：O（N*logN）,空间复杂度为O（n）;