一、算法思想
首先将初始序列的n个记录看成是n个有序的子序列，每个子序列的长度为1，然后两两归并，得到n/2向上取整个长度为2（n为奇数时，最后一个序列的长度为1）的有序子序列。在此基础上，再对长度为2的有序子序列进行两两归并，得到若干个长度为4的有序子序列。以此类推，知道得到一个长度为n的有序序列为止。
二、算法实现
1.递归实现
#include<stdio.h> #include<stdlib.h> void Merg(int arry[],int temp[],int left,int right,int mid) { int i = left,j = right,k = mid + 1; while(i < mid + 1 && k < right + 1) { if(arry[i] < arry[j]) { temp[k++] = arry[i++]; } else temp[k++] = arry[j++]; } while(i < mid + 1) { temp[k++] = arry[i++]; } while(j < right + 1) { temp[k++] = arry[j+1]; } for(i = left;i<right;i++) { arry[i] = temp[i]; } } void Mergsort(int arry[],int temp[],int left,int right) { int mid; if(left < right) { Mergsort(arry,temp,left,mid); Mergsort(arry,temp,mid+1,right); Merg(arry,temp,left,right,mid); } }整个算法的执行顺序借助下图可以表示为如下图所示的1--20
其中每个Merge所代表的数组如下
2.非递归实现
#incldue <iostream> using namespace std; /*将a开头的长为length的数组和b开头长度为size的数组合并为长度为n的数组*/ void Merge(int *data,int a,int b,int length,int n) { int size; if(b+length-1 >= n-1) { size = n - b; } else { size = length; } int* temp = new int[length+size]; int i=0,j=0; while(i<=length-1 && j<= size - 1) { if(data[a+i] <= data[b+i]) { temp[i+j] = data[a+i]; i++; } else { temp[i+j] = data[a+i]; i++; } } if(j == size) { memcpy(temp+i+j,data+b+j,(size -j) * sizeof(int)) } else if(i == length) { memcpy(temp + i + j,data + b + j,(right - j)*sizeof(int)); } memcpy(data + a,temp,(right + length)*sizeof(int)); delete[] temp; } void Mergesort(int* data,int n) { int step = 1; while(step < n) { for(int i=0;i<n-step-1;i+=2*step) { Merge(data,i,i+step,step,n); } step*=2; } }三、时间复杂度分析
从整个排序过程可以看出归并排序的时间主要花在划分时间序列、两个子序列的排序过程以及合并过程。划分序列的时间为常数，可以忽略。
归并过程的时间是随着记录序列的长度n而线性增长的。因此，对一个长度为n的记录序列进行归并排序，调用一趟归并排序的操作是调用n/2h向下取整次Merge算法，将记录序列arry前后相邻且长度为h的有序段进行两两归并，得到前后相邻，长度为2h的有序段，并存放在arry中,其时间复杂度O(N)。整个归并排序需进行logn（底数为2）趟二路归并，所以归并排序总的时间复杂度为O（nlogn）.
四、稳定性
从算法中可以看出，每次都是从左半部分开始进行归并，且当左半部分和右半部分的关键字相等时左半部分优先，所以整个排序算法是稳定的。
