一文读懂『归并排序』算法（Merge Sort）（含算法模板）

归并排序（Merge Sort）是建立在归并操作上的一种有效，稳定的排序算法，该算法是采用 分治法（Divide and Conquer） 的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。

与上一讲 【Y总/算法基础课/学习笔记】快速排序（Quick Sort）（含算法模板）相比，快速排序是将序列想划分成两个子序列，再递归使子序列有序；而归并排序是先使子序列有序，再进行合并。

二、 算法基本思想和流程（时间复杂度 $O(nlogn)$ ）

• Step1——确定分界点mid（三种常用的方法）：q[l]、q[(l+r)/2]、q[r]，或者随机确定；
• Step2——将待排序列调整成 left 和 right 两个子序列，递归排序 left 和 right ；
• Step3——归并（合二为一），Finish！

2. 难点/关键点：步骤三的归并方法（双指针算法，$O(n)$ ）

步骤二结束后会得到两个排好序的子序列 list1 和 list2 ，采用 双指针算法 将其合二为一：

• 定义两个指针：i 和 j，分别指向两个子序列的起始元素，另外定义一个新序列 temp 用来存储归并结果；
• 两指针指向的元素进行比较：
  • 若 *i <= *j ，将该元素放入到 temp 中，并且 i++ ；
  • 若 *i > *j ，将该元素放入到 temp 中，并且 j++ ；
• 不断循环进行上述比较操作，直到某一个指针指向了该子序列的末尾，则将另一个序列的剩余部分全部按顺序放入 temp 中即可，所得的 temp 序列为归并排序的结果。

举个例子如下，易于理解：

三、 归并排序模板（背诵）

模板题： AcWing 787. 归并排序

注意：此题数据较大且多，输入输出建议使用 scanf 和 printf ，要使用C++的 cin 和 cout 需要进行速度优化，参考另一篇博文： C++ 输入输出（cin & cout）加速/效率优化 。

模板一：

void merge_sort(int q[], int l, int r)
{
	// 1.判边界
    if (l >= r) return;
	
	// 2.定分界点
    int mid = l + r >> 1;
	// 递归排序子序列
    merge_sort(q, l, mid), merge_sort(q, mid + 1, r);

	// 3.归并排序（双指针法）
    int k = 0, i = l, j = mid + 1;
    while (i <= mid && j <= r)
        if (q[i] <= q[j]) tmp[k ++ ] = q[i ++ ];
        else tmp[k ++ ] = q[j ++ ];
    // 某个子序列走到最后了，将另一个序列剩余部分加入到 tmp 中
    while (i <= mid) tmp[k ++ ] = q[i ++ ];
    while (j <= r) tmp[k ++ ] = q[j ++ ];
	
	// 将排序结果 tmp 重新覆盖掉 q
    for (i = l, j = 0; i <= r; i ++, j ++ ) q[i] = tmp[j];
}

模板二：

void merge_sort(int q[], int l, int r)
{
	// 1.判边界
    if (l >= r) return;
	
	// 2.定分界点
    int mid = l + r + 1 >> 1;
	// 递归排序子序列
    merge_sort(q, l, mid - 1), merge_sort(q, mid, r);

	// 3.归并排序（双指针法）
    int k = 0, i = l, j = mid;
    while (i <= mid - 1 && j <= r)
        if (q[i] <= q[j]) tmp[k ++ ] = q[i ++ ];
        else tmp[k ++ ] = q[j ++ ];
    // 某个子序列走到最后了，将另一个序列剩余部分加入到 tmp 中
    while (i <= mid - 1) tmp[k ++ ] = q[i ++ ];
    while (j <= r) tmp[k ++ ] = q[j ++ ];
	
	// 将排序结果 tmp 重新覆盖掉 q
    for (i = l, j = 0; i <= r; i ++, j ++ ) q[i] = tmp[j];
}

【分析避免边界问题】

• 当递归取的 merge_sort(q, l, mid), merge_sort(q, mid + 1, r);，则为了避免陷入死循环，取中间值需要下取整 x = q[l + r >> 1]
• 当递归取的 merge_sort(q, l, mid - 1), merge_sort(q, mid, r);，则为了避免陷入死循环，取中间值需要上取整 x = q[l + r + 1 >> 1]