思想
先对少数几个元素通过两两合并的方式进行排序，形成一个长度稍大一些的有序序列。
然后在此基础上，对两个长度稍大一些的有序序列再进行两两合并，形成一个长度更大的有序序列，直到覆盖整个数组的大小为止，归并排序就完成了。
单趟排序的实现分析
单趟排序的目的：
在数组arr[low...mid]有序和arr[mid...high]有序的前提下，使数组arr[low...high]有序。
单趟归并的过程如下：
准备：
排序前创建有一个和原数组a长度相同的辅助数组aux。
辅助数组aux的任务有两项：比较元素大小， 并在aux中逐个取得有序的元素放入原数组a中 （通过1使aux和a在low-high的位置是完全相同的！这是实现的基础）
过程：
- 首先将原数组中的待排序序列拷贝进辅助数组的相同位置中，即将a[low...high]拷贝进aux[low...high]中
- 因为aux[low...high]由两段有序的序列：aux[low...mid]和aux[mid...high]组成， 这里称之为aux1和aux2,
- 我们要做的就是从aux1和aux2的头部元素开始，比较双方元素的大小。将较小的元素放入原数组a中，并取得较小元素的下一个元素位置index；重复多次直到其中一个数组存放完毕。（因为前提是aux1和aux2都是有序的，所以通过这种方法我们能得到更长的有序序列）
- 如果aux的两段序列中，其中一段中的所有元素都已"比较"完了, 取得另一段序列中剩下的元素，全部放入原数组a的剩余位置。
- 对于3步骤的具体实现：
-
- 设置两个游标变量,i 和 j，开始时分别指向aux[low]和aux[mid]；分别代表左游标和右游标。
-
- 设置游标k用于确定在a中放置元素的位置（在a中进行），k在开始时候指向a[low]
-
- 如果aux1[i]<aux[j];则a[k]=aux1[i]; k++;i++;
-
- 如果aux1[i]>aux[j];则a[k]=aux2[i]; k++;j++;
代码：
/**
* @description: 完成一趟合并
* @param a 输入数组
* @param low,mid,high a[low...high] 是待排序序列， 其中a[low...mid]和 a[mid+1...high]已有序
*/
int aux[1000000];
void merge (int a [],int low,int mid,int high) {
for(int k=low;k<=high;k++){
aux[k] = a[k]; // 将待排序序列a[low...high]拷贝到辅助数组的相同位置
}
int i = low; // 游标i,开始时指向待排序序列中左半边的头元素
int j = mid+1; // 游标j,开始时指向待排序序列中右半边的头元素
for(int k=low;k<=high;k++){
if(i>mid){
a[k] = aux[j++]; // 左半边用尽
}else if(j>high){
a[k] = aux[i++]; // 右半边用尽
}else if(aux[j]<aux[i]){
a[k] = aux[j++]; // 右半边当前元素小于左半边当前元素， 取右半边元素
}else {
a[k] = aux[i++]; // 右半边当前元素大于等于左半边当前元素，取左半边元素
}
}
}
}
基于递归的归并排序（自顶向下）
核心思想是将两个有序的数列合并成一个大的有序的序列。通过递归，层层合并，即为归并。
最关键的是sort(int a [], int low,int high)方法里面的三行代码：
sort(a,low,mid); //对左半边序列递归
sort(a,mid+1,high);//对右半边序列递归
merge(a,low,mid,high);//、单趟合并操作。
代码
#include <iostream>
using namespace std;
int a[1000000];
int aux[1000000];
/**
* @description: 完成一趟合并
* @param a 输入数组
* @param low,mid,high a[low...high] 是待排序序列， 其中a[low...mid]和 a[mid+1...high]已有序
*/
void merge(int a[], int low, int mid, int high)
{
for (int k = low; k <= high; k++)
{
aux[k] = a[k]; // 将待排序序列a[low...high]拷贝到辅助数组的相同位置
}
int i = low;
// 游标i,开始时指向待排序序列中左半边的头元素
int j = mid + 1;
// 游标j,开始时指向待排序序列中右半边的头元素
for (int k = low; k <= high; k++)
{
if (i > mid)
{
a[k] = aux[j++]; // 左半边用尽
}
else if (j > high)
{
a[k] = aux[i++]; // 右半边用尽
}
else if (aux[j] < aux[i])
{
a[k] = aux[j++]; // 右半边当前元素小于左半边当前元素， 取右半边元素
}
else
{
a[k] = aux[i++]; // 右半边当前元素大于等于左半边当前元素，取左半边元素
}
}
}
/**
* @description: 基于递归的归并排序算法
*/
void merge_sort(int arr[], int L, int R)
{
if (L >= R)
return;// 终止递归的条件
int mid = (R + L) / 2;// 取得序列中间的元素
merge_sort(arr, L, mid);// 对左半边递归
merge_sort(arr, mid + 1, R); // 对右半边递归
merge(arr, L, mid, R);// 单趟合并
}
int main()
{
int n;
cin >> n;
for (int i = 0; i < n; i++)
cin >> a[i];
merge_sort(a, 0, n - 1);
for (int i = 0; i < n; i++)
cout << a[i] << " ";
return 0;
}