二路归并排序主要运用了“分治算法”，分治算法就是将一个大的问题划分为n个规模较小而结构相似的子问题。
这些子问题解决的方法都是类似的，解决掉这些小的问题之后，归并子问题的结果，就得到了“大”问题的解。
二路归并排序主旨是“分解”与“归并”
分解：
1.将一个数组分成两个数组，分别对两个数组进行排序。
2.循环第一步，直到划分出来的“小数组”只包含一个元素，只有一个元素的数组默认为已经排好序。
归并：
1.将两个有序的数组合并到一个大的数组中。
2.从最小的只包含一个元素的数组开始两两合并。此时，合并好的数组也是有序的。
图1. 归并排序过程 图2. 合并两个有序数组
举例说明：
1.图中原始数组为{2,4,7,5,8,1,3,6}，数组中元素的个数为8个。首先将8个元素的数组二分，每次分解后，
数组中元素的数目为原数组的一半。直到分解为只含有一个元素的数组。
2.将小的数组按序合并，每次合并后数组的大小为上层数组的一倍。此时数组中的元素都是按序排列的。
3.在合并两个有序数组。如图2
下面的是自顶向下递归实现2路归并排序：
#include <iostream>
using namespace std;
void Merge(int * a, int low, int mid, int high)
{
int i = low, j = mid + 1, p = 0;//对应a数组的下标
int * r = new int[high - low + 1];//申请另一个对应大小的数组来存放排好序的数据
while (i <= mid && j <= high)
{
r[p++] = (a[i] <= a[j]) ? a[i++] : a[j++];
}
while (i <= mid)
r[p++] = a[i++];
while (j <= high)
r[p++] = a[j++];
for (p = 0, i = low; i <= high; p++, i++)
a[i] = r[p];//最后再把有序数据存进a数组中，使得a数组对应部分数据有序
delete[] r;
}
//自顶向下(递归实现)
void MSort(int *a, int low, int high)
{
if (low<high)
{
int mid = (low + high) / 2;
MSort(a, low, mid);
MSort(a, mid + 1, high);
Merge(a, low, mid, high);
}
}
int _tmain(int argc, _TCHAR* argv[])
{
int a[] = { 2,4,7,5,8,1,3,6 };
int n = sizeof(a) / sizeof(int);
MSort(a, 0, n - 1);
for (int i = 0; i<n; i++)
cout << a[i] << " ";
cout << endl;
system("PAUSE");
return 0;
}
参考资料：《算法导论》2.1章节