歸并排序思路：將序列從中間分割成兩部分，分別遞歸歸并排序，后將兩個子序列合并。
歸并排序雖然是經典排序里比較最少的算法，但有大量的復制操作，還需要O(N)的輔助空間，從而一般不用于主存，也不利于c++編程。
Java中比較操作耗時多，而復制則耗時少，從而歸并排序是Java中主要排序方法。
而在C++ STL中快速排序是基本排序方法。
1
/**//***************************************************************************/
2/**//* Merge_Sort.h */
3/**//* 歸并排序：將序列從中間分割成兩部分，分別遞歸歸并排序，后將兩個子序列合并*/
4/**//* 算法分析：T(N) = 2T(N/2) + cN , T(N) = Nlog(N) */
5/**//* 附加空間為N: 一般不能用于主存 */
6/**//* 復制運算比較多，不適合c++ */
7
/***************************************************************************/
8
9#ifndef MERGE_SORT_H
10#define MERGE_SORT_H
11
12#include "typedef.h"
13#include <vector>
14
15/**//* 將分別歸并排序的子序列合并 */
16void Merge(T*a, int begin, int middle, int end)
17
{
18
std::vector<T> temp; //輔助空間
19 int i = begin, j = middle+1;
20 int size = end - begin + 1;
21
22
/**//* 同時遍歷兩個序列，將小的存入輔助向量中 */
23 while(i <= middle && j <= end)
24 {
25 if(a[i] <= a[j]) temp.push_back(a[i++]);
26 else temp.push_back(a[j++]);
27
}
28
29 /**//* 將子序列的剩余的元素直接存入輔助向量中，此時另一個已為空*/
30 while(j <= end) temp.push_back(a[j++]);
31 while(i <= middle) temp.push_back(a[i++]);
32
33 /**//* 復制回原序列*/
34 for(i = 0; i != size; ++i)
35 a[begin+i] = temp[i];
36 /**//* 釋放輔助空間 */
37 temp.clear();
38}
39
40void Merge_Sort_s(T* a, int begin, int end)
41{
42 /**//* 遞歸調用 */
43 if(begin < end)
44 {
45 int middle = (begin+end)/2;
46 Merge_Sort_s(a,begin,middle);
47 Merge_Sort_s(a,middle+1,end);
48 Merge(a,begin,middle,end);
49 }
50}
51
52/**//* 統一的排序法接口 */
53void Merge_Sort(T*a, int n)
54{
55 Merge_Sort_s(a,0,n-1);
56}
57
58#endif