Dutor

#include <iostream>
#include <ctime>
 
using namespace std;
 
template <class T>
class Merger
{
public:
	Merger(T* array, size_t n):extra(new T[n/2]) //~ 归并需要O(n)的额外空间
	{
		sub_Merger(array, n); //~ 调用递归子函数
	}
	~Merger()
	{
		delete [] extra; //~ 释放内存
	}
private:
	T* extra;
	Merger();
	void sub_Merger(T* array, size_t n);
};
 
template <class T>
void Merger<T>::sub_Merger(T * array, size_t n)
{
	if(n == 1) //~ 递归终止
		return ;
	else if(n == 2)  //~ 递归终止
	{
		if( array[0] > array[1] )
		{
			T tmp = array[0];
			array[0] = array[1];
			array[1] = tmp;
		}
	}
	else
	{
		/* 将数组均分为两部分，分别排好，然后归并*/
		size_t m = n / 2;
		//~ 分别排序
		sub_Merger(array, m + 1);
		sub_Merger(array + m + 1, n - m - 1);
		//~ 归并
		size_t i = 0, j = m + 1, k = 0;
		memcpy(extra, array, (m + 1)* sizeof(T));
		while( i <= m && j < n)
		{
			array[k++] = extra[i] < array[j] ? extra[i++]:array[j++];
		}
		while(i <= m)
		{
			array[k++] = extra[i++];
		}
	}
}
 
int main()
{
	srand((unsigned)time(0));
	const int N(100);
	int demo[N];
	for(int i = 0; i < N; ++i)
	{
		demo[i] = rand()%N;
	}
	Merger<int>(demo, N);
	for(int i = 0; i < N; ++i)
		cout<<demo[i]<<endl;
    return 0;
}