原文

思想

先对少数几个元素通过两两合并的方式进行排序，形成一个长度稍大一些的有序序列。
然后在此基础上，对两个长度稍大一些的有序序列再进行两两合并，形成一个长度更大的有序序列，直到覆盖整个数组的大小为止，归并排序就完成了。

单趟排序的实现分析

单趟排序的目的：
在数组arr[low...mid]有序和arr[mid...high]有序的前提下，使数组arr[low...high]有序。
单趟归并的过程如下：
准备：
排序前创建有一个和原数组a长度相同的辅助数组aux。

辅助数组aux的任务有两项：比较元素大小， 并在aux中逐个取得有序的元素放入原数组a中 （通过1使aux和a在low-high的位置是完全相同的！这是实现的基础）

过程：

1. 首先将原数组中的待排序序列拷贝进辅助数组的相同位置中，即将a[low...high]拷贝进aux[low...high]中
2. 因为aux[low...high]由两段有序的序列：aux[low...mid]和aux[mid...high]组成， 这里称之为aux1和aux2,
3. 我们要做的就是从aux1和aux2的头部元素开始，比较双方元素的大小。将较小的元素放入原数组a中，并取得较小元素的下一个元素位置index；重复多次直到其中一个数组存放完毕。（因为前提是aux1和aux2都是有序的，所以通过这种方法我们能得到更长的有序序列）
4. 如果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;
}

改进