1.归并排序
（1）选取分界点：mid = (l + r) // 2
（2）递归排序：left、right
（3）归并：将左右合二为一
↓（指针i）
——————————（有序的 Left ）
——————————（有序的 Right ）
↑ (指针j）
Result [ ]
（a）如果 Left [ i ] <= Right [ j ]，Left [ i ] 加入到 Result 中，i 后移
（b）反之，如果 Left [ i ] > Right [ j ]，Right [ j ] 加入到 Result 中，j 后移
（c）直到其中一个指针达到尾部
（d）将 Left 或 Right 中剩余部分依次加入到 Result 尾部
2.归并排序 / 快速排序的时间复杂度：nlog(n)
每层会将数组分成各1/2的两块，所以一共有 log2(n) 层；
每层都需要遍历一遍，时间复杂度是 O(n) ；
所以整体的时间复杂度为确定值 O(nlogn)
对快速排序来讲，原理类似，但此时 O(nlogn) 为时间复杂度的期望，对不同的输入数据表现不同
3.归并排序Python代码实现
输入样例：
5
3 1 2 4 5
输出样例：
1 2 3 4 5
Python3：
def merge_sort(a):
if len(a) <= 1: return
mid = len(a) // 2
l = a[:mid]
r = a[mid:]
# 递归处理左右两段
merge_sort(l)
merge_sort(r)
i = j = k = 0
# merge
while(i < len(l) and j < len(r)):
if l[i] <= r[j]:
a[k] = l[i]
i += 1
else:
a[k] = r[j]
j += 1
k += 1
while(i < len(l)):
a[k] = l[i]
i += 1
k += 1
while(j < len(r)):
a[k] = r[j]
j += 1
k += 1
n = int(input())
a = [int(i) for i in input().split()]
merge_sort(a)
for i in range(len(a)):
print(a[i], end = ' ')
4.逆序对的数量
逆序对总共分为三种：
（1）左半边内部的逆序对：merge_sort(L, mid)
（2）右半边内部的逆序对：merge_sort(mid + 1, R)
（3）在两边的逆序对：
L：——————————（指针指在 i ）
R：——————————（指针指在 j ）
当 L [ i ] < R [ j ] 时，i 与 i 后所有 Left 中元素均为 R [ j ] 对应的逆序对，即：s += mid - i + 1
5.逆序对的数量Python代码实现
输入样例：
6
2 3 4 5 6 1
输出样例：
5
Python3：
def merge_sort(a):
s = 0
if len(a) <= 1: return 0
mid = len(a) // 2
l = a[:mid]
r = a[mid:]
s += merge_sort(l) + merge_sort(r)
i = j = k = 0
while(i < len(l) and j < len(r)):
if(l[i] <= r[j]):
a[k] = l[i]
i += 1
k += 1
else:
a[k] = r[j]
j += 1
k += 1
s += len(l) - i
while(i < len(l)):
a[k] = l[i]
i += 1
k += 1
while(j < len(r)):
a[k] = r[j]
j += 1
k += 1
return s
n = int(input())
a = [int(i) for i in input().split()]
print(merge_sort(a))
