归并排序

原题：AcWing 787. 归并排序

1、确定边界

2、递归排序

3、归并

#include <iostream>

using namespace std;

const int N = 1e6;
int q[N], tmp[N], ans = 0;

void merge_sort(int n[], int f, int l){
    if(f == l) return;
    int t = 0, mid = (f + l) / 2, i = f, j = mid + 1;
    merge_sort(n, f, mid);
    merge_sort(n, j, l);
    while(i <= mid && j <= l)
        if (n[i] < n[j]) tmp[t++] = n[i++];
        else tmp[t++] = n[j++], ans += mid - i + 1;
    while(i <= mid) tmp[t++] = n[i++];
    while(j <= l) tmp[t++] = n[j++];
    for(i = f, j = 0; i <= l; i++, j++)
        n[i] = tmp[j];
}

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