归并排序

Luogu P1177
将读入的N个数从小到大排序后输出

输入格式

第一行为一个正整数N。
第二行包含N个空格隔开的正整数a_i ，为你需要进行排序的数。

输出格式

将给定的N个数从小到大输出，数之间空格隔开，行末换行且无空格。

对于20%的数据，有1≤N≤10³;

对于100%的数据，有1≤N≤10⁵ ，1≤a_i≤10⁹。

样例

输入
5
5 2 4 5 1

输出
1 2 4 4 5

归并排序主要利用分治思想，时间复杂度为O(nlogn)。

int n, a[100010], b[100010];    /* 此处a，b为辅助数组 */

void merge_sort(int q[], int l, int r){
    if(l >= r) return;
    int mid = (l + r) >> 1;
    merge_sort(q, l, mid);
    merge_sort(q, mid + 1, r);  /* 递归拆分 */

    int i = l, j = mid + 1, k = l;  /* 合并 */
    while(i <= mid && j <= r){
        if(a[i] <= a[j]) b[k++] = a[i++];
        else b[k++] = a[j++];
    }

    while(i <= mid) b[k++] = a[i++];
    while(j <= r) b[k++] = a[j++];
    for(i = l; i <= r; i++) a[i] = b[i];
}

思路如下

1. 对数列不断进行等长拆分，直到为一个数的长度;
2. 回溯时，按升序合并左右两段。
3. 重复以上两个过程，直到递归结束。

划分

合并：
1. i,j 分别指向a的左右段起点，k指向b的起点。
2. 枚举a数组，如果左数≤右数，把左数放入b数组，否则，把右数放入b数组。
3. 把左段或右端剩余的数放入b数组。
4. 把b数组的当前段复制回a数组。

完整实现如下

#include <iostream>
using namespace std;
int n, a[100010], b[100010];

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);

    int i = l, j = mid + 1, k = l;
    while(i <= mid && j <= r)
        if(a[i] <= a[j]) b[k++] = a[i++];
        else b[k++] = a[j++];

    while(i <= mid) b[k++] = a[i++];
    while(j <= r) b[k++] = a[j++];
    for(i = l; i <= r; i++) a[i] = b[i];
}

int main(){
    cin >> n;
    for(int i = 0; i < n; i++) scanf("%d", &a[i]);
    merge_sort(0, n - 1);
    for(int i = 0; i < n; i++) printf("%d ", a[i]);
    return 0;
}