归并排序

(双指针+递归) $O(nlogn)$

C++ 代码

void merge_sort(int q[],int left,int right)
{
    if(left >= right) return;

    int mid = (left + right)>> 1;

    merge_sort(q,left,mid),merge_sort(q,mid+1,right);
    int k = 0,i = left,j = mid+1;
    while(i <= mid && j<= right)
        if(q[i] <= q[j]) tmp[k++] = q[i++];
        else tmp[k++] = q[j++];
    while(i <= mid) tmp[k++] = q[i++];
    while(j <= right) tmp[k++] = q[j++];

    for(i = left,j = 0;i<=right;i++,j++) q[i] = tmp[j];

}