Merge_sort

基于分治，以及递归

时间复杂度

时间复杂度：O(nlogn),要会主定理算

code

int w[100001]; // 辅助数组，用于合并时临时存储

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

    for(i = l , j = 0 ; j < k ; i ++ , j++) q[i] = w[j];
}