选择排序和插入排序对n个元素的操作次数都与n*n成正比，效率比较低。自底向上合并排序次数少得多。

一般地，令A为需要排序的n个元素的数组，首先合并成n/2个连续元素对，生成大小为2的n/2个排序序列，如果剩余一个元素，就让它进入下一轮迭代。然后合并n/4个连续的2元素对的序列，生成n/4个大小为4的排序序列。如果剩余一或两个元素，那么他们将进入下一轮迭代；如果剩余三个元素，将两个（已排序的）元素和另一个元素合并成一个3元素的排序序列。继续这一过程，在第j次迭代中，合并n/(2^j)对大小为2^(j-1)的排序序列，生成大小为2^j的n/(2^j)个排序序列。如果有k个剩余元素，1<=k<=2^(j-1)，则将它们放在下一次合并中；如果有k个剩余元素，2^(j-1)<k<2^j，则将它们合并，形成一个大小为k的排序序列。

算法BOTTOMUPSORT：算法用变量s存储被合并序列的大小，开始时将s置为1，每次执行外面的while循环时被乘以2。i+1,i+s和i+t用来定义两个要排序的序列的边界。当n不是t的倍数时，执行第8步。这种情况下，如果剩余元素的数目（即n-i）大于s，就要在大小为s的序列和剩余元素之间再进行一次排序。

#include

using namespace std;

void MERGE(int*,int,int,int);

int main()

{

     int A[11]={6,10,9,5,3,11,4,8,1,2,7};

     int t=1;

     int s;

     int i;

     while(t<10)

     {

         s=t;

         t=2*s;

         i=0;

         while(i+t<11)

         {

              MERGE(A,i,i+s-1,i+t-1);//此处调用合并两个已排序的表的算法函数

              i=i+t;

         }

         if(i+s<10)

              MERGE(A,i,i+s-1,10);

     }

     for(i=0;i<11;++i)

         cout<<A[i]<<' ';

     return 0;

}

void MERGE(int* A,int p,int q,int r)

{

     int B[11];

     int s=p;

     int t=q+1;

     int k=p;

     while(s<=q&&t<=r)

         if(A[s]<=A[t])

              B[k++]=A[s++];

         else

              B[k++]=A[t++];

     if(s==q+1)

         for(int i=0;i< P>

              B[k+i]=A[t+i];

     else

         for(int i=0;i< P>

              B[k+i]=A[s+i];

     for(int i=p;i< P>

         A[i]=B[i];

}