前言
将待排序序列R[0...n-1]看成是n个长度为1的有序序列，将相邻的有序表成对归并，得到n/2个长度为2的有序表；将这些有序序列再次归并，得到n/4个长度为4的有序序列；如此反复进行下去，最后得到一个长度为n的有序序列。
参考资料
1. 编码
//display
template<typename T> struct Disp
{
void operator()(T value)
{
cout << value << "\t";
}
};
void Merge(std::vector<int>& vec, int left, int midle, int right)
{
int i = left; //第一个序列的起始位置
int j = midle+1; //第二个序列的起始位置
int pos = 0; //临时数组下标计数
int* temp_array = new int[right-left+1]; //临时数组
while(i<=midle && j<=right) //遍历两个序列，将小的数字放在前面
{
if(vec[i] < vec[j])
{
temp_array[pos++] = vec[i++];
}
else
{
temp_array[pos++] = vec[j++];
}
}
while(i<=midle) //第一个序列没走完，那么将第一个序列的元素添加到后面去
temp_array[pos++] = vec[i++];
while(j<=right) //第二个序列没走完，那么将第二个序列的元素添加到后面去
temp_array[pos++] = vec[j++];
//更新原始的数组
for(int i=0, k=left; k<=right; k++, i++)
vec[k] = temp_array[i];
delete[] temp_array;
temp_array = nullptr;
}
void MergeSort(std::vector<int>& vec)
{
int len(vec.size());
if(len == 0) return;
cout << "display origin array:" << endl;
for_each(vec.begin(), vec.end(), Disp<int>()); //打印原始的数据
for (int gap = 1; gap<len; gap=2*gap)
{
int i = 0;
// 归并gap长度的两个相邻子表
for (i=0; i+2*gap-1<len; i=i+2*gap)
{
Merge(vec, i, i+gap-1, i+2*gap-1);
}
// 余下两个子表，后者长度小于gap
if (i+gap-1 < len)
{
Merge(vec, i, i+gap-1, len-1);
}
}
cout << "\narray sorted:" << endl;
for_each(vec.begin(), vec.end(), Disp<int>());
}
