快速排序和归并排序都使用分治思想：把大问题拆成小问题，再通过递归完成排序。不过，它们完成主要工作的时机不同：快排先划分，再递归；归并先递归，再合并。

本文采用适合竞赛入门的写法：数组设为全局变量，排序范围统一为闭区间 [l, r]，函数只传左右端点。快速排序使用普通 while，归并排序的合并函数单独编写。

一、约定与准备

下面的模板按从小到大排序，默认数据存放在 a[1] 到 a[n]。

#include <bits/stdc++.h>
using namespace std;

const int N = 1000005;
int a[N], b[N];

b 是归并排序使用的辅助数组。数组长度应根据题目调整；下标从 1 开始时，需要保证 n < N。bits/stdc++.h 适用于常见的 GNU C++ 竞赛环境；若使用标准头文件，本文的完整程序只需要 <iostream> 和 <utility>。

二、快速排序：先划分，再递归

1. 基本思路

从当前区间中选一个基准值 x，让左指针 i 向右找不小于 x 的元素，让右指针 j 向左找不大于 x 的元素。

如果两个指针还没有交错，就交换这两个元素，再让指针各移动一步。划分完成后，分别递归排序左右两段。

这里选取中间位置的元素作为基准。需要注意：中间位置的元素不一定是整个区间的中位数，因此不保证每次都能均分区间。

2. 代码模板

void quicksort(int l, int r) {
    if (l >= r) return;

    int i = l, j = r;
    int x = a[l + (r - l) / 2];

    while (i <= j) {
        while (a[i] < x) i++;
        while (a[j] > x) j--;

        if (i <= j) {
            swap(a[i], a[j]);
            i++;
            j--;
        }
    }

    quicksort(l, j);
    quicksort(i, r);
}

调用方式：

quicksort(1, n);

3. 为什么要保存基准值？

应该保存中间位置的值：

int x = a[l + (r - l) / 2];

不能只保存下标，然后一直与 a[mid] 比较，因为交换可能改变这个位置的元素，导致前后使用不同的基准。

也要区分“值”和“下标”：如果变量已经保存了基准值，就直接比较 a[i] < x，不能写成 a[i] < a[x]。

4. 为什么内部使用 while？

while (a[i] < x) i++;
while (a[j] > x) j--;

这两行需要连续跳过已经在正确一侧的元素，直到找到需要交换的位置。若改成 if，每次只移动一步，随后可能交换到不该交换的元素。

比较使用严格的 < 和 >，遇到等于基准的元素也会停下，再通过交换后的指针移动继续处理。

5. 为什么两处都写 i <= j？

外层的条件是：

while (i <= j)

[i, j] 表示尚未处理的部分。i == j 时，还剩一个位置；使用 <= 可以把它也处理完，使循环结束时一定满足 i > j。

内层的条件是：

if (i <= j)

内部扫描可能使指针交错，因此交换前需要再次判断。如果指针恰好相遇，两次扫描都停下，说明该位置的值等于 x。此时交换自身没有影响，关键是继续执行 i++ 和 j--。

如果保留外层 <=，却把内层改成 <，遇到上述相遇情况时指针不会移动，就会死循环。

例如，排序 [3, 2, 1]，基准为 2：

第一次交换： [1, 2, 3]
指针移动后： i = 2，j = 2
再处理一次： 中间元素与自身交换，i = 3，j = 1
循环结束

严格来说，在其余代码保持不变时，外层改成 < 也能正确排序，但指针相遇时会提前退出，使这个位置同时进入左右递归区间。模板保留 <=，便于统一理解为“处理到指针交错，递归区间不重叠”。外层的等号并不是为了防止死循环。

6. 为什么递归 [l, j] 和 [i, r]？

划分过程中，已经处理的部分满足：

• [l, i-1] 中的元素都不大于 x。
• [j+1, r] 中的元素都不小于 x。

循环结束后，i > j，于是剩下需要分别排序的两段是：

[l ........ j]     [i ........ r]
    都 <= x             都 >= x
  内部未必有序        内部未必有序

如果两指针相遇后各移动一步，中间会留下一个不进入递归的位置；它的值等于 x，不需要再排。

因此递归写成：

quicksort(l, j);
quicksort(i, r);

这份模板不保证 i 是基准值最终就位的位置，不能随意改成 quicksort(l, i-1) 和 quicksort(i+1, r)。不同快排写法的划分方式与递归边界需要配套使用。

三、归并排序：先递归，再合并

1. 基本思路

归并排序将 [l, r] 分成 [l, mid] 和 [mid+1, r]，先递归排好这两段，再把两个有序区间合并。

合并时，比较两段当前最前面的元素，把较小的放入辅助数组。当其中一段取完，直接复制另一段的剩余元素，最后写回原数组。

2. 代码模板

// 合并已经有序的 [l, mid] 和 [mid + 1, r]
void hebin(int l, int r) {
    int mid = l + (r - l) / 2;
    int i = l, j = mid + 1, p = l;

    while (i <= mid && j <= r) {
        if (a[i] <= a[j]) b[p++] = a[i++];
        else b[p++] = a[j++];
    }

    while (i <= mid) b[p++] = a[i++];
    while (j <= r) b[p++] = a[j++];

    for (int t = l; t <= r; t++)
        a[t] = b[t];
}

void guibin(int l, int r) {
    if (l >= r) return;

    int mid = l + (r - l) / 2;
    guibin(l, mid);
    guibin(mid + 1, r);
    hebin(l, r);
}

调用方式：

guibin(1, n);

hebin 必须在左右两段分别有序后调用。它在内部计算与递归函数相同的中点，因此只需要接收 l、r 两个参数。

3. 为什么剩余元素要用 while 复制？

while (i <= mid) b[p++] = a[i++];
while (j <= r) b[p++] = a[j++];

主循环结束时，至少一段已经取完，另一段可能还剩多个元素。用 if 只会复制一个，使用 while 才能全部复制。

两段本来就已经有序，所以剩余元素可以直接按原顺序追加。这两个循环的先后顺序不影响结果。

4. i++、j++ 会不会导致越界？

以左半段为例：

while (i <= mid) b[p++] = a[i++];

i++ 先使用当前值，再增加。当 i == mid 时，这次访问的是合法位置 a[mid]，之后 i 才变成 mid+1。下一次条件不成立，循环退出。

右半段同理，最多读取 a[r]。

整个合并过程恰好写入 r-l+1 个元素，p 从 l 开始，因此最后写入的是 b[r]。写完后 p 变成 r+1，但不会再用这个值访问数组。

下标变量超出当前区间，并不等于发生越界访问；关键是有没有用它访问不合法的位置。

5. 辅助数组的下标要对应

本模板让 p 从 l 开始，使原数组与辅助数组使用相同下标：

a[l..r]  →  b[l..r]  →  a[l..r]

所以回写可以直接写成：

for (int t = l; t <= r; t++)
    a[t] = b[t];

如果选择让 p 从 0 开始，结果就存放在 b[0..r-l]，回写必须相应改成：

for (int t = l; t <= r; t++)
    a[t] = b[t - l];

两种方式都可以，但不能混用。闭区间的右端点也要处理，循环条件应为 t <= r。

6. 为什么使用 <=，而不是 <？

两种比较方式都能得到正确的数值顺序，但 <= 能保证这份归并排序的稳定性。

稳定排序指：值相等的元素，在排序后仍保持原来的先后顺序。例如用甲、乙标记两个值同为 2 的元素：

原顺序：2甲  2乙

如果 2甲 位于左半段、2乙 位于右半段，使用 <= 会优先取左边的 2甲，保留原顺序；使用 < 则会先取右边的 2乙，改变相对顺序。

单纯排序整数时，这个区别看不出来；当元素还带着姓名、编号等信息，并按某个字段排序时，稳定性就有意义。

四、复杂度与特点

快排通过交换原数组中的元素完成划分，不需要长度为 n 的辅助数组，但仍然需要递归栈空间。固定选择中间位置的值也不能避免最坏情况。

归并每次从中间划分，递归层数为 O(log n)；每层合并总工作量为 O(n)，因此最坏时间复杂度仍为 O(n log n)。同一个全局辅助数组可以重复使用，无需在每次递归中重新分配或清空。

五、完整使用示例

将上面的全局数组与所需排序函数放在 main 前面，再加入：

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];

    guibin(1, n);
    // 使用快速排序时，将上一行替换为 quicksort(1, n);

    for (int i = 1; i <= n; i++) {
        if (i > 1) cout << ' ';
        cout << a[i];
    }
    cout << '\n';
    return 0;
}

输入：

6
5 2 4 2 1 3

输出：

1 2 2 3 4 5

记忆模板时，快排重点记住“保存基准值、双指针扫描、交换后移动、按 j 和 i 递归”；归并重点记住“先排两半、合并有序段、复制剩余元素、按对应下标回写”。理解这些步骤，才能在修改模板时判断边界是否仍然正确。