归并排序思路：将序列从中间分割成两部分，分别递归归并排序，后将两个子序列合并。
归并排序虽然是经典排序里比较最少的算法，但有大量的复制操作，还需要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