【题解】归并排序

归并排序

1. 找分界点， mid = l + r >> 1 。
2. 左右分别递归排序， merge_sort(l, mid), merge_sort(mid + 1, r);。
3. 将排好序的左右两边合并在一起。

细节处理

1. backup 数组只在过程中起辅助排序作用，每次都从 1 开始，包括 排序 与 合并 过程。
2. 原数组要在对应的范围内（l, r）操作，包括 排序 与 合并 过程。

归并排序 c++ 82ms

#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <cstdio>
#include <cmath>
#include <map>

using namespace std;
typedef long long LL;

const int N = 100000 + 5;

int n;
int num[N], backup[N];

void merge_sort(int l, int r)
{
    // 递归结束条件
    if (l >= r) return ;
    
    int mid = l + r >> 1;
    merge_sort(l, mid);
    merge_sort(mid + 1, r);
    
    // 备份数组只在过程中起辅助排序作用，每次都从1开始
    int i = l, j = mid + 1, k = 1;
    while (i <= mid && j <= r) 
    {
        if (num[i] < num[j]) backup[k ++ ] = num[i ++ ];
        else backup[k ++ ] = num[j ++ ]; 
    }
    while (i <= mid) backup[k ++ ] = num[i ++ ];
    while (j <= r) backup[k ++ ] = num[j ++ ];
    
    // 注意此处将备份的数组复制回原数组时，要复制到对应位置
    for (i = l, j = 1; i <= r; i ++, j ++ ) num[i] = backup[j];
    return ;
}

int main()
{
    cin >> n;
    for (int i = 1; i <= n; i ++ ) scanf("%d", &num[i]);

    merge_sort(1, n);
    for (int i = 1; i <= n; i ++ ) printf("%d ", num[i]);
    return 0;
}