参考：
归并排序详解及应用
相关题目：
912. 排序数组
315. 计算右侧小于当前元素的个数
493. 翻转对
327. 区间和的个数
归并排序其实就是二叉树的后序遍历，左右子树分别排序（sort），然后再后序遍历位置合并（merge）两个左右子树。
利用左右子树有序的特征，在merge阶段可以适当改进来做一些拓展应用，这里罗列的 leetcode 315题、leetcode 493题、leetcode 327题，均是利用该框架，详细见代码：
# 912. 排序数组
class Solution:
def sortArray(self, nums: List[int]) -> List[int]:
# 辅助数组，开辟内存空间
self.temp = [None] * len(nums)
# 归并排序对数组进行原地排序
self.sort(nums, 0, len(nums)-1)
return nums
# 归并排序
def sort(self, arr, lo, hi):
if lo == hi:
return
mid = lo + (hi-lo)//2
self.sort(arr, lo, mid)
self.sort(arr, mid+1, hi)
self.merge(arr, lo, mid, hi)
# 合并两个有序数组 arr[lo..mid] 和 arr[mid+1..hi]
def merge(self, arr, lo, mid, hi):
# 将两个有序数组复制到 辅助数组上
for i in range(lo, hi+1):
self.temp[i] = arr[i]
i, j = lo, mid+1
for p in range(lo, hi+1):
if i == mid+1:
# 左半边数组已全部被合并
arr[p] = self.temp[j]
j += 1
elif j == hi+1:
# 右半边数组已全部被合并
arr[p] = self.temp[i]
i += 1
elif self.temp[i] > self.temp[j]:
arr[p] = self.temp[j]
j += 1
else:
arr[p] = self.temp[i]
i += 1
# 315. 计算右侧小于当前元素的个数
class Solution:
def countSmaller(self, nums: List[int]) -> List[int]:
class Pair:
def __init__(self, val, idx):
self.val = val
self.idx = idx
# 归并排序
def sort(arr, lo, hi):
if lo == hi:
return
mid = lo + (hi-lo)//2
sort(arr, lo, mid)
sort(arr, mid+1, hi)
merge(arr, lo, mid, hi)
# 合并两个有序数组 arr[lo..mid] 和 arr[mid+1..hi]
def merge(arr, lo, mid, hi):
# 将两个有序数组复制到 辅助数组上
for i in range(lo, hi+1):
temp[i] = arr[i]
i, j = lo, mid+1
for p in range(lo, hi+1):
if i == mid+1:
# 左半边数组已全部被合并
arr[p] = temp[j]
j += 1
elif j == hi+1:
# 右半边数组已全部被合并
arr[p] = temp[i]
i += 1
# 更新count数组
count[arr[p].idx] += hi-mid
elif temp[i].val > temp[j].val:
arr[p] = temp[j]
j += 1
else:
arr[p] = temp[i]
i += 1
# 更新count数组
count[arr[p].idx] += j-mid-1
# 归并排序要用到的辅助数组
temp = [Pair(0, 0) for _ in range(len(nums))]
# 记录每个元素后面比自己小的元素个数
count = [0 for _ in range(len(nums))]
arr = [Pair(nums[idx], idx) for idx in range(len(nums))]
# 执行归并排序
sort(arr, 0, len(nums)-1)
return count
# 493. 翻转对
class Solution:
def reversePairs(self, nums: List[int]) -> int:
self.res = 0
# 归并排序
def sort(arr, lo, hi):
if lo == hi:
return
mid = lo + (hi-lo)//2
sort(arr, lo, mid)
sort(arr, mid+1, hi)
merge(arr, lo, mid, hi)
# 合并两个有序数组 arr[lo..mid] 和 arr[mid+1..hi]
def merge(arr, lo, mid, hi):
# 将两个有序数组复制到 辅助数组上
for i in range(lo, hi+1):
temp[i] = arr[i]
# 在合并有序数组之前，加点私货
end = mid + 1
for i in range(lo, mid+1):
# 对于左半边的每个 nums[i]，都去右半边寻找符合条件的元素
while end<=hi and nums[i] > 2*nums[end]:
end += 1
# 更新全局变量
self.res += (end - (mid+1))
i, j = lo, mid+1
for p in range(lo, hi+1):
if i == mid+1:
# 左半边数组已全部被合并
arr[p] = temp[j]
j += 1
elif j == hi+1:
# 右半边数组已全部被合并
arr[p] = temp[i]
i += 1
elif temp[i] > temp[j]:
arr[p] = temp[j]
j += 1
else:
arr[p] = temp[i]
i += 1
# 归并排序要用到的辅助数组
temp = [None for _ in range(len(nums))]
# 执行归并排序
sort(nums, 0, len(nums)-1)
return self.res
# 327. 区间和的个数
class Solution:
def countRangeSum(self, nums: List[int], lower: int, upper: int) -> int:
self.res = 0
self.lower = lower
self.upper = upper
preSum = [0] * (len(nums) + 1)
for i in range(len(nums)):
preSum[i + 1] = nums[i] + preSum[i]
# 归并排序
def sort(arr, lo, hi):
if lo == hi:
return
mid = lo + (hi-lo)//2
sort(arr, lo, mid)
sort(arr, mid+1, hi)
merge(arr, lo, mid, hi)
# 合并两个有序数组 arr[lo..mid] 和 arr[mid+1..hi]
def merge(arr, lo, mid, hi):
# 将两个有序数组复制到 辅助数组上
for i in range(lo, hi+1):
temp[i] = arr[i]
# 在合并有序数组之前，加点私货
start = end = mid + 1
for i in range(lo, mid+1):
# 维护左闭右开区间 [start, end) 中的元素和 nums[i] 的差在 [lower, upper] 中
while start<=hi and arr[start]-arr[i] < self.lower:
start += 1
while end<=hi and arr[end]-arr[i] <= self.upper:
end += 1
# 更新全局变量
self.res += (end - start)
i, j = lo, mid+1
for p in range(lo, hi+1):
if i == mid+1:
# 左半边数组已全部被合并
arr[p] = temp[j]
j += 1
elif j == hi+1:
# 右半边数组已全部被合并
arr[p] = temp[i]
i += 1
elif temp[i] > temp[j]:
arr[p] = temp[j]
j += 1
else:
arr[p] = temp[i]
i += 1
# 归并排序要用到的辅助数组
temp = [None for _ in range(len(preSum))]
# 执行归并排序
sort(preSum, 0, len(preSum)-1)
return self.res