归并排序

注意预定义tmp[N], 调用merge_sort(q, 0, n-1);

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 ) {
          // 注意q[i] <= q[j] 
        if ( q[i] <= q[j] ) tmp[k++] = q[i++];
        else tmp[k++] = q[j++]; 
        // 求逆序对，else中加上 cnt += mid - i +1;
    }
    while ( i <= mid ) tmp[k++] = q[i++];
    while ( j <= r ) tmp[k++]  =q[j++];

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

STL中的归并排序函数

stable_sort(a.begin(),a.end(),cmp);