合并排序

算法思路：

递归分前半和后半排序然后合并。

应用：

1. 排序
2. 求逆序数

注意事项：

1. merge函数中更改输入nums。
2. line 15的等号决定是否stable sort。

Python代码：

def merge_sort(self, nums: List[int]):
	self.m_sort(nums, 0, len(nums) - 1)

def m_sort(self, nums: List[int], start: int, end: int):
	if start >= end:
		return
	mid = start + (end - start) // 2
	self.m_sort(nums, start, mid)
	self.m_sort(nums, mid + 1, end)
	self.merge(nums, start, mid, end)

def merge(self, nums: List[int], start: int, mid: int, end: int):
	i, j, res = start, mid + 1, []
	while i <= mid and j <= end:  # = decides if it is stable sort
		if nums[i] <= nums[j]:
			res.append(nums[i])
			i += 1
		else:
			res.append(nums[j])
			j += 1
	while i <= mid:
		res.append(nums[i])
		i += 1
	while j <= end:
		res.append(nums[j])
		j += 1
	nums[start:end + 1] = res

算法分析：

时间复杂度为O(nlogn)，空间复杂度O(n)。