归并排序

算法思想：

分治法，将一个序列分为两部分，分别排序，然后合并已排序序列。

算法实现：

 1 void merge(int A[],int p,int q,int r )
 2 {
 3     int * AA = new int[r-p+1];
 4     int i = p;
 5     int j = q;
 6     int k = 0;
 7 
 8     while( i < q && j <= r )
 9     {
10         if( A[i] <= A[j] ) AA[k++] = A[i++];
11         else AA[k++] = A[j++];
12     }
13     while( i < q )
14     {
15         AA[k++] = A[i++];
16     }
17     while( j <= r )
18     {
19         AA[k++] = A[j++];
20     }
21 
22     memcpy(A,AA,(r-p+1)*sizeof(int));
23     delete []AA;
24 }
25 
26 void merge_sort( int A[], int n )
27 {
28     if( n < 2 ) return ;
29     int mid = n/2;
30     merge_sort( A, mid);
31     merge_sort( A+mid, n-mid);
32     merge( A, 0, mid, n-1 );
33 }

考虑优化点：

合并时每次申请、释放内存会严重影响运行效率，可以考虑在外部传入空间用于合并操作
在子序列数量较小时，可以使用插入排序来优化提升效率
合并后将序列复制到原序列中，该操作会增加nlgn的数据复制，可以参考stl中stable_sort的实现方式，避免或减少数据复制

算法复杂度：

平均：O(nlgn)

最差：O(nlgn)

最优：O(nlgn)

空间复杂度:O(n)

使用场景：

归并排序由于有比较优的时间复杂度，并且具有排序稳定性(相同key值元素不改变位置)，因此一般用在要求稳定性的大规模数据排序中。

STL实现：

stl的stable_sort内部采用了归并算法实现，在有足够归并空间时，其复杂度为O(nlgn)，但当空间不足时，其复杂度为O(n lgn lgn )