【模版】归并排序

归并排序,它有两大核心操作.

• 一个是将数组一分为二,一个无序的数组成为两个数组。
• 另外一个操作就是,合二为一,将两个有序数组合并成为一个有序数组。

时间复杂度情况：

最好和最快情况都是:O(NlogN)

代码模版如下

int arr[N], temp[N];

void merge_sort(int arr[], int l, int r) {
    if (l >= r)
        return;
//递归结束条件
    int mid = l + r >> 1;

    merge_sort(arr, l, mid), merge_sort(arr, mid + 1, r);
//递归处理子问题
    int k = 0, i = l, j = mid + 1;
//归并
    while (i <= mid && j <= r) {
        if (arr[i] <= arr[j])
            temp[k ++] = arr[i ++];
        else
            temp[k ++] = arr[j ++];
    }
//收尾
    while (i <= mid)
        temp[k ++] = arr[i ++];
    while (j <= r)
        temp[k ++] = arr[j ++];

    for (int i = l, j = 0; i <= r; i++, j++)
        arr[i] = temp[j];
}

图解如下：

更详细的见下面的连接：

AcWing 787. 归并排序的证明与边界分析 - AcWing