[AcWing 787]归并排序

#include<iostream>
using namespace std;

const int N = 100010;
int n;
int q[N], tmp[N];

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 k = 0, i = l, j = mid+1; //双指针算法 进行归并
    while(i <= mid && j <= r){
        if(q[i] <= q[j]){
            tmp[k++] = q[i++];
        }
        else{
            tmp[k++] = q[j++];
        }
    }
    while(i <= mid) tmp[k++] = q[i++];
    while(j <= r) tmp[k++] = q[j++];
    
    for(int i = l, j = 0; i <= r; i++,j++) q[i] = tmp[j];
}

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


/*
听课记录：
第一步：确定分界点 mid = (l+r)/2  是下标的中间值（而快排确定的是数组里面的一个值作为中间值）
第二步：递归排序 左边left 和 右边right
第三步：归并，把两个有序的数组合并为一个有序的数组 ---> 合二为一※  采用双指针算法  时间复杂度O(n)

归并排序是稳定的
快速排序是不稳定的  （但快排中Ai变成<Ai,i> 即双关键字排序 则是稳定的）

快速排序  平均时间复杂度O(n*logn)
归并排序  时间复杂度O(n*logn)
每一层是O(n) 共logn层 ---> O(n*logn)

*/