归并排序是一种基于“归并”思想的排序方法，本节主要介绍其中最基本的2-路归并排序。2-路归并排序的原理是，将序列两两分组，将序列归并为[n/2]个组，组内单独排序；然后将这些组再两两归并，生成[n/4]个组，组内再单独排序；以此类推，直到只剩下一个组为止，其核心在于如何将两个有序序列合并成一个有序序列。归并排序的时间复杂度为O(nlogn)。
下面来看一个例子，要将序列{66，12，33，57，64，27，18）进行2-路归并排序。
①第一趟。两两分组，得到四组：{66，12}、{33，57}、{64，27}、{18}，组内单独排序，
得到新序列{{12,66}，{33，57}，{27，64}，{18}}。
②第二趟。将四个组继续两两分组，得到两组：{12，66，33，57}、{27，64，18}，组内单
独排序，得到新序列{{12，33，57，66}，{18，27，64}}
③第三趟，将两个组继续两两分组，得到一组：{12，33，57，66，18，27，64}，组内单独排
序，得到新序列112.18.27.33.57、64.661，算法结束。
从上面的过程中可以发现，2-路归并排序的核心在于如何将两个有序序列合并为一个有
序序列，而这个过程在上一小节的“序列合并问题”中已经讲解。接下来讨论2-路归并排序
的递归版本和非递归版本的具体实现。
1.递归实现
2-路归并排序的递归写法非常简单，只需要反复将当前区间[eft，nightl分为两半，对两个
子区间et mid]与[mid+l，rnght]分别递归进行归并排序，然后将两个已经有序的子区间合并
为有序序列即可，代码如下，其中merge函数为上一节的代码改编而来，请读者注意与上一
节代码的对比：
递归实现：
#include<cstdio> const int maxn = 100; //将数组A的[L1,R1]和[L2,R2]区间合并为有序区间（此处L2即为R1+1） void merge(int A[],int L1,int R1,int L2,int R2) { int i=L1,j=L2; //i指向A[l1],j指向A[L2] int temp[maxn],index = 0; //temp临时存放合并后的数组，index为其下标 while(i<=R1&&j<=R2){ if(A[i]<=A[j]) { //如果A[i]<=A[j] temp[index++]=A[i++]; //将A[i]加入序列temp }else{ // 如果A[i]>A[j] temp[index++]=A[j++]; //将A[j]加入序列temp } } while(i<=R1) temp[index++] = A[i++]; //将[L1,R1]的剩余元素加入序列temp while(j<=R2) temp[index++] = A[j++]; //将[L2,R2]的剩余元素加入序列temp for(i=0;i<index;i++){ A[L1+i] = temp[i]; //将合并后的序列赋值回数组A } } //将array数组当前区间[left,right]进行归并排序 void mergeSort(int A[],int left,int right) { if(left<right){ //只要left<right int mid = (left+right)/2; //取[left,right]的中点 mergeSort(A,left,mid); //递归，将左子区间[left,mid]归并排序 mergeSort(A,mid+1,right); //递归，将右子区间[mid+1,right]归并排序 merge(A,left,mid,mid+1,right); //将左子区间和右子区间合并 } } int main(){ const int n=7; int A[n] = {66,12,33,57,64,27,18}; mergeSort(A,0,6); for(int i=1;i<n;i++){ printf("%d\n",A[i]); } return 0; }
非递归实现：
2-路归并排序的非递归实现主要考虑到这样一点：每次分组时组内元素个数上限都是
的幂次。于是就可以想到这样的思路：令步长step的初值为2，然后将数组中每step个元
作为一组，将其内部进行排序（即把左step/2个元素与右step/2个元素合并，而若元素
数不超过step/2，则不操作)；再令step乘以2，重复上面的操作，直到step/2超过元素
数n(结合代码想一想为什么此处是step/2)。代码如下(想一想如果数组下标从0开始，
该修改哪些地方?)
#include<cstdio> #include<cmath> using namespace std; const int maxn = 100; const int n=8; int min(int a,int b) { return a<b? a:b; } //将数组A的[L1,R1]和[L2,R2]区间合并为有序区间（此处L2即为R1+1） void merge(int A[],int L1,int R1,int L2,int R2) { int i=L1,j=L2; //i指向A[l1],j指向A[L2] int temp[maxn],index = 0; //temp临时存放合并后的数组，index为其下标 while(i<=R1&&j<=R2){ if(A[i]<=A[j]) { //如果A[i]<=A[j] temp[index++]=A[i++]; //将A[i]加入序列temp }else{ // 如果A[i]>A[j] temp[index++]=A[j++]; //将A[j]加入序列temp } } while(i<=R1) temp[index++] = A[i++]; //将[L1,R1]的剩余元素加入序列temp while(j<=R2) temp[index++] = A[j++]; //将[L2,R2]的剩余元素加入序列temp for(i=0;i<index;i++){ A[L1+i] = temp[i]; //将合并后的序列赋值回数组A } } void mergeSort(int A[]) { //step为组内元素个数，step/2为左子区间元素个数，注意等号可以不取 for(int step=2;step/2<n;step*=2) { //每step个元素一组，组内前step/2和后step/2个元素进行合并 for(int i=0;i<n;i+=step){ //对每一组 int mid = i+step/2-1; //左子区间元素个数为step/2 if(mid+1<=n) { //右子区间存在元素则合并 //左子区间为[i,mid],右子区间为[mid+1,min(i+step-1,n)] merge(A,i,mid,mid+1,min(i+step-1,n)); } } } } int main(){ int A[n] = {66,12,33,57,64,27,18}; mergeSort(A); for(int i=1;i<n;i++){ printf("%d\n",A[i]); } return 0; }
当然，如果题目中只要求给出归并排序每一趟结東时的序列，那么完全可以使用sort函数来代替 merge函数(只要时间限制允许)，如下所示:
void mergeSort(int A[]) { //step为组内元素个数，step/2为左子区间元素个数，注意等号可以不取 for(int step=2;step/2<n;step*=2) { //每step个元素一组，组内[i,min(i+step,n+1)]进行排序 for(int i=1;i<=n;i+=step) { sort(A+i,A+min(i+step,n+1)); } //此处可以输出归并排序的某一趟结束的序列 } }
原文：https://www.cnblogs.com/migang/p/14702712.html