代码已经在 GITHUB 开源，👉点击直达👈。

〇、算法步骤

归并排序也属于分治算法中的一种：

  1. 确定分界点 mid，将数组划分为“左子数组”和“右子数组”。
  2. 递归排序“左子数组”和“右子数组”，得到自身有序的两个子数组。
  3. 最后，归并得到的“左子数组”和“右子数组”即可得到完整的有序数组。

一、算法模板

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
/**
 * @brief 归并排序
 * @param arr 待排序的数组
 * @param temp 辅助数组（必须与待排序的数组空间大小一致）
 * @param left 左边界
 * @param right 右边界
 */
static void merge_sort(int arr[], int temp[], int left, int right) {
    // 递归终止条件
    if (left >= right) return;

    // 确定分界点
    int mid = (left + right) / 2;

    // 递归左右子数组
    merge_sort(arr, temp, left, mid);
    merge_sort(arr, temp, mid + 1, right);

    // 初始化变量
    int k = 0,          // k 代表 temp 数组中已经存储的元素个数，也作为 temp 数组的存储索引
        i = left,       // i 代表“左子数组”的起点索引
        j = mid + 1;    // j 达标“右子数组”的起点索引

    // 归并
    while (i <= mid && j <= right) {    // 将有序的“左/右子数组”元素归并到 temp 数组
        if (arr[i] <= arr[j]) {         // 如果左子数组索引指向的元素更小，就复制左子数组索引指向的元素
            temp[k++] = arr[i++];
        }
        else {                          // 否则复制右子数组索引指向的元素
            temp[k++] = arr[j++];
        }
    }
    while (i <= mid) {                  // 可能最后“左子数组”元素还没归并完
        temp[k++] = arr[i++];
    }
    while (j <= right) {                // 可能最后“右子数组”元素还没归并完
        temp[k++] = arr[j++];
    }

    // 将归并的结果复制回原数组
    for (int ai = left, ti = 0; ai <= right; ai++, ti++) {  // ai 为 arr 索引，ti 为 temp 索引
        arr[ai] = temp[ti];
    }
}

二、算法练习题

  1. AcWing 787. 归并排序
  2. AcWing 788. 逆序对的数量