基本思想：通过分块治理，现将分开的部分变得有序，再来进行合并，称为归并排序。
二路归并：通过将待排序咧分成两部分进行归并排序，称为二路归并排序。
将每个元素拆分成大小为1的分区
递归地合并相邻分区
遍历 i=左侧首项位置 到右侧末项位置
如果 左侧首项的值 <= 右侧首项的值
拷贝左侧首项的值
否则：拷贝右侧首项的值；增加逆序数
a = 待排序列
def msort(l, r):
if l == r:
return
mid = (l+r)>>1
msort(l, mid)
most(mid+1, r)
i, j, k = l, mid+1, 1
while i<=mid and j<=r:
if a[i] <= a[j]:
b[k]=a[i]
i++
else:
b[k]=a[j]
j++
k++
while i<=mid: b[k++]=a[i++]
while j<=r: b[k++]=a[j++]
for i in range(r): a[i] = b[i]
most(0, len(a))
print(a)
稳定排序
时间复杂度\(O(nlog_2n)\)
空间复杂度\(O(n)\)，因采用递归，还需占用栈空间。
逆序对问题
a = 待排序列
ans=0
def msort(l, r):
if l == r:
return
mid = (l+r)>>1
msort(l, mid)
most(mid+1, r)
i, j, k = l, mid+1, 1
while i<=mid and j<=r:
if a[i] <= a[j]:
b[k]=a[i]
i++
else:
b[k]=a[j]
ans += mid-i+1
j++
k++
while i<=mid: b[k++]=a[i++]
while j<=r: b[k++]=a[j++]
for i in range(r): a[i] = b[i]
most(0, len(ans))
print(a)