额外空间O(n) 数组等分为两份 递归排序 O(n)合并两个长度为n/2的有序数组 求逆序对的个数:有O(n log n)的做法 inplace_merge 原地归并排序 inplace_merge(a + l, a + m, a + r) 保证 a[l] a[l+1] .. a[m-1] 升序 a[m] a[m+1] .. a[r-1] 升序 合并2个序列
归并排序可以用来求逆序对(逆序对也可以用树状数组解决)