合并排序基本思想：
将待排序元素分成大小大致相同（可以不等长）的两个子集和，分别对两个子集合进行排序，最终将排好序的子集合合并成所要求的排好序的集合。
递归版：
void MergeSort(int a[],int left,int right)
{
if(left<right)
{
int i=(left+right)/2;
MergeSort(a,left,i);
MergeSort(a,i+1,right);
Merge(a,b,left,i,right);
Copy(a,b,left,right); //copy b to a
}
}
可见递归版的合并排序是严格按照其思想完成的。
最坏情况下：T(n)=2T(n/2)+O(n);
则其时间复杂度O(nlogn)
非递归：
void MergeSort(int a[],int n)
{
int *b=new int[n];
int s=1;
while(s<n)
{
MergePass(a,b,s,n); //合并到数组b
s+=s; //这里不是自增，而是成倍的增加</span>
MergePass(b,a,s,n); //合并到数组A
s+=s;
}
}
void MergePass(int x[],int y[],int s,int n)
{
int i=0;
while(i<=n-2*s)
{
Merge(x,y,i,i+s-1,i+2*s-1); //这里只能完成标准区间内的合并排序，如果有多余的元素便顾及不了
i=i+2*s;
}
if(i+s<n) //解决最后一个元素(区间块)合并而设计的，i=0,s=8,n=9
Merge(x,y,i,i+s-1,n-1);
else
for(int j=i;j<=n-1;j++) //未到合并最后一个元素的直接复制
y[j]=x[j];
}
void Merge(int c[],int d[],int l,int m,int r)
{
//合并c[l:m]和c[m+1:r]到d[l:r]
int i=l,j=m+1,k=r;
while((i<=m)&&(j<=r))
{
if(c[i]<=c[j])
d[l++]=c[i++];
else
d[l++]=c[j++];
}
if(i>m)
for(int q=j;q<=r;q++) //i>m说明i已经复制到d中了，所以要把剩下的j复制到b中,并且此时c中元素是有序的，所以可以直接复制
d[l++]=c[q];
else
for(int p=i;p<=m;p++)
d[l++]=c[p];
}
分析一下时间复杂度：
纵向：1->2->4->8....n 共logn次
横向：包括比较和循环复制，最多都不超过n
所以时间复杂度也为O(nlogn)
但在现实中给定数组中，肯定存在已排好序的子数组段，如果将其利用起来，就避免了无意义的比较。
例如：a[]={0,-1,9,3,6,4,2,5,7};
自然排好序的子数组段有{0}{-1,9}{3,6}{4}{2,5,7}.可以用一次对数组a的线性扫描，找出这些已排好序的子数组段，然后两两合并，构成更大已排好序的数组。
{-1,0,9}{3,4,6}{2,5,7}->{-1,0,3,4,6,9}{2,5,7}->{-1,0,2,3,4,5,6,7,9}
核心代码：
void GetBPoint(int a[],int b[],int n,int &m) //线性扫描a[]，记录下已排好序的子数组段下标
{
int j=0;
b[j++]=0;
for(int i=0;i<n-1;i++)
{
if(a[i+1]<a[i])
b[j++]=i+1;
}
m=j;
PrintArray(b,j);
}
void MergeSort(int a[],int n)
{
int *b=new int[n];
int s=1;
while(s<t_m)
{
MergePass(a,b,s,n); //合并到数组b
s+=s;
MergePass(b,a,s,n); //合并到数组a
s+=s;
}
delete[] b;
}
void MergePass(int x[],int y[],int s,int n)
{
int i=0;
while(i<=t_m-2*s)
{
int r=((i+2*s)<t_m)?t[i+2*s]:n; //当自然排好序片段为偶数时，就r=n,表示刚好两两合并成功，最后没有多余的子数组段
Merge(x,y,t[i],t[i+s]-1,r-1);
i=i+2*s;
}
if(i+s<t_m)
Merge(x,y,t[i],t[i+s]-1,n-1);
else
if(i<t_m) //i<t_m表示有多余的子数组段，则直接复制在y[]后，因为该子数组已排好序了
{
for(int j=t[i];j<=n-1;j++)
y[j]=x[j];
}
}
时间复杂度分析：
由于利用了自然排好序的子数组段，所以在自然合并排序中，合并的次数要少很多，即使是在某一具体实例中，而不是所谓的平均情况下。
尽管理论上分析时间复杂度也为O(nlogn)，但是实际中，一定会存在自然排好序片段，这样的话时间就会大大降低了。
极端的例子，如果n元素数组已经排好序了，该算法并不需要合并，而合并排序算法还需要进行logn合并，
所以自然合并排序算法需要O(n)（时间仅仅花在扫描上了），合并排序算法需要O(nlogn)时间
自然合并排序完整代码：
#include<iostream>
using namespace std;
#define N 9
int t_m; //自然合并排序中线性扫描的标记数
int t[N];
void Merge(int c[],int d[],int l,int m,int r)
{
//合并c[l:m]和c[m+1:r]到d[l:r]
int i=l,j=m+1,k=r;
while((i<=m)&&(j<=r))
{
if(c[i]<=c[j])
d[l++]=c[i++];
else
d[l++]=c[j++];
}
if(i>m)
for(int q=j;q<=r;q++) //i>m说明i已经复制到d中了，所以要把剩下的j复制到b中,并且此时c中元素是有序的，所以可以直接复制
d[l++]=c[q];
else
for(int p=i;p<=m;p++)
d[l++]=c[p];
}
void PrintArray(int a[],int n)
{
for(int i=0;i<n;i++)
cout<<a[i]<<" ";
cout<<endl;
}
void GetBPoint(int a[],int b[],int n,int &m)
{
int j=0;
b[j++]=0;
for(int i=0;i<n-1;i++)
{
if(a[i+1]<a[i])
b[j++]=i+1;
}
m=j;
PrintArray(b,j);
}
void MergePass(int x[],int y[],int s,int n)
{
int i=0;
while(i<=t_m-2*s)
{
int r=((i+2*s)<t_m)?t[i+2*s]:n;
Merge(x,y,t[i],t[i+s]-1,r-1);
i=i+2*s;
}
if(i+s<t_m)
Merge(x,y,t[i],t[i+s]-1,n-1);
else
if(i<t_m)
{
for(int j=t[i];j<=n-1;j++)
y[j]=x[j];
}
}
void MergeSort(int a[],int n)
{
int *b=new int[n];
int s=1;
while(s<t_m)
{
MergePass(a,b,s,n); //合并到数组b
s+=s;
MergePass(b,a,s,n); //合并到数组a
s+=s;
}
delete[] b;
}
int main()
{
int n=9;
int a[]={0,-1,9,3,4,6,2,5,7}; //自然排好序子数组段为偶数个
//int a[]={0,-1,1,3,8,4,2,5,7}; 奇数
PrintArray(a,n);
GetBPoint(a,t,n,t_m);
MergeSort(a,n);
PrintArray(a,n);
return 0;
}