心得

快排的递归发生在最后，是先排序后递归，而归并是先递归后排序

C++ 代码

#include <iostream>

using namespace std;

const int N = 1e5 + 10;
int q[N];
int temp[N];

void merge_sort(int i ,int j){
    if(i >= j) return ;
    int l = i,mid = (i + j) / 2,r = mid + 1;
    merge_sort(i , mid);
    merge_sort(mid + 1 , j);
    int k = 0;
    while(l <= mid && r <= j){
        if(q[l] <= q[r]) temp[k++] = q[l++];
        else temp[k++] = q[r++];
    }
    while(l <= mid){
        temp[k++] = q[l++];
    }
    while(r <= j){
        temp[k++] = q[r++];
    }
    for(int idx = 0,l = i;l <= j;++idx,++l){
        q[l] = temp[idx];
    }
}

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

    for(int i = 0;i < n;++i){
        cout << q[i] <<" ";
    }
    return 0;

}