O(n2)的冒泡，选择，插入，先不贴，先贴归并，快排，堆排，

O(nlog(n))

归并排序

二路归并递归写法：时间O(nlog(n))，稳定，总时间O(nlog),空间：O(n+log(n))，n为内存，log(n)为栈空间

#include<bits/stdc++.h>
using namespace std;

//归并过程
void merge(int arr[], int l, int mid, int r){
    int len=r-l+1;//合并长度
    vector<int> help; //临时数组
    int lindex = l;
    int rindex = mid+1;
    while(lindex<=mid && rindex<=r){
        if(arr[lindex]<arr[rindex]){
            help.push_back(arr[lindex++]);
        }else{
            help.push_back(arr[rindex++]);
        }
    }
    while(lindex<=mid){
        help.push_back(arr[lindex++]);
    }
    while(rindex<=r){
        help.push_back(arr[rindex++]);
    }
    for(int i=0;i<len;i++){
        arr[l+i]=help[i];
    }
}

void mergesort(int arr[], int l,int r){
    if(l==r) return;
    int mid=(r+l)/2;
    mergesort(arr,l,mid);
    mergesort(arr,mid+1,r);
    merge(arr,l,mid,r);
}

int main(){
    int n;
    while(cin >> n){
        int arr[n];
        for(int i = 0; i < n; i++) cin>>arr[i];
        mergesort(arr, 0,n-1);//排序数组，和起始终止de下标

        for(int i = 0; i < n; i++){
            cout << arr[i] << " ";
        }
        cout << endl;
    }
    return 0;
}
/*
10
8 6 7 9 2 3 4 1 0 5
*/