定义：
归并（Merge）排序法是将两个（或两个以上）有序表合并成一个新的有序表，即把待排序序列分为若干个子序列，每个子序列是有序的。然后再把有序子序列合并为整体有序序列。 （从百度百科上摘抄下来的）
基本的实现可以如下表示：
void merger_sort(Iterator first,Iterator last)
{
if(last-first<=1)
return ;
Iterator middle=first+(last-first)/2;
merger_sort(first,middle);
merger_sort(middle,last);
sort(first,middle,last,*first);
}
首先吧区间的左半边排序 即：merger_sort(first,middle);
然后把区间的右半边排序 即：merger_sort(middle,last);
最后再把两个区间合并： sort(first,middle,last,*first);
合并的算法如下：
for( i=0;front!=mid&&middle!=last;++i)
{
if(*front>*middle)
{
tempContainer[i]=*middle;
++middle;
}
else
{
tempContainer[i]=*front;
++front;
}
}
if(front==mid)
{
for(;middle!=last;++middle)
tempContainer[i++]=*middle;
}
else
for(;front!=mid;++front)
tempContainer[i++]=*front;
首先是：
if(*front>*middle)
{
tempContainer[i]=*middle;
++middle;
}
else
{
tempContainer[i]=*front;
++front;
}
然后把剩下的部分直接赋给剩下的空间：
if(front==mid)
{
for(;middle!=last;++middle)
tempContainer[i++]=*middle;
}
else
for(;front!=mid;++front)
tempContainer[i++]=*front;
完整代码：
测试代码：