1：合并排序

    合并排序算法使用分治策略实现对n个元素进行排序的算法。其基本思想是：将待排序元素分成大小大致相同的两个子集合，分别对两个子集合进行排序，最后总将排好序的子集合合并成所要求的排好序的集合。算法描述如下：

 void MergeSort(Typr 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);   //合并到数组b

                        Copy(a,b,left,right);    //复制回数组a

               }

}

void Merge(Type c[],Type d[],int l,int m,int r)

{

              int i=l,j=m+1,k=1;

              while((i<=m)&&(j<=r))

              {

                     if(c[i]<=c[j])    d[k++]=c[i++];

                     else d[k++]=c[j++];

              }

              if(i>m)   for(int q=j;q<=r;q++)    d[k++]=c[q];

              else for(int q=i;q<=m;q++)             d[k++]=c[q];

}

时间复杂度：O(nlogn)

各种排序算法总结