归并排序

基本概念

归并排序（Merge Sort）基本思想：
利用分治法，将数组递归地一分为二，直至每个子数组只包含一个元素。随后，将这些有序子数组两两合并，最终得到一个整体有序的数组。

算法步骤

假设数组的元素个数为 n 个，则归并排序的算法步骤如下：

分解过程：递归地将当前数组平分为两部分，直到每个子数组只包含一个元素为止。
1. 找到数组的中间位置 mid，将数组划分为左、右两个子数组left_nums 和 right_nums。
2. 分别对 left_nums 和 right_numsr递归执行分解操作。
3. 最终将原数组拆分为 n 个长度为 1 的有序子数组。
归并过程：从长度为 1 的有序子数组开始，逐步将相邻的有序子数组两两合并，最终合并为一个长度为 n 的有序数组。
1. 新建数组 nums 用于存放合并后的有序结果。
2. 设置两个指针 left_i 和 right_i，分别指向 left_nums 和 right_nums的起始位置。
3. 比较两个指针所指元素，将较小者加入结果数组 numsnums，并将对应指针后移一位。
4. 重复上述操作，直到某一指针到达对应子数组末尾。
5. 将另一个子数组剩余的所有元素依次加入结果数组 nums。
6. 返回合并后的有序数组 nums。

内部实现：

class solution:
	def merge(self,left_nums:[int],right_nums:[int]):
		nums=[]
		left_i,right_i=0,0
		while left_i < len(left_nums)and right_i<len(right_nums):
			if left_nums[left_i]<=right_nums[right_i]:
				nums.append(left_nums[left_i])
				left_i+=1
			else:
				nums.append(right_nums[right_i])
				right_i+=1
		while left_i <len(left_nums):
			nums.append(left_nums[left_i])
			left_i+=1
		while right_i <len(right_nums):
			nums.append(right_nums[right_i])
			right_i+=1
		return nums
	def mergesort(self,nums:[int])->[int]:
		if len(nums)<=1:
			return nums
		mid = len(nums)//2
		left_nums=self.mergesort(nums[0:mid])
		right_nums=self.mergesort(nums[mid:])
		return self.merge(left_nums,right_nums)
	def sortrray(self,nums:[int])->[int]:
		return self.mergesort(nums)

复杂度分析：

指标	复杂度	说明
最佳时间复杂度	O(nlog⁡n)	无论数组状态如何，都需要 log⁡n 次分解和 n 次合并
最坏时间复杂度	O(nlog⁡n)	无论数组状态如何，都需要 log⁡n次分解和 n 次合并
平均时间复杂度	O(nlog⁡n)	归并排序的时间复杂度与数据状态无关
空间复杂度	O(n)	需要额外的辅助数组来存储合并结果
稳定性	稳定	合并过程中相等元素的相对顺序保持不变
补充说明：

归并排序采用分治策略，将数组递归地分成两半，每次分解的时间复杂度为 O(1)，分解次数为logn。
合并过程的时间复杂度为 O(n)，因为需要遍历两个子数组的所有元素。
总的时间复杂度为 O(nlogn)，这是基于比较的排序算法的理论下界。

适用场景：

大规模数据排序（n>1000）
对稳定性有要求的场景
外部排序（数据无法全部加载到内存）
链表排序
归并排序是一种高效稳定的排序算法，采用分治策略将数组递归分解后合并排序。
优点：
- 时间复杂度稳定，始终为 O(nlogn)
- 稳定排序，相等元素相对位置不变
- 适合大规模数据排序
- 可用于外部排序和链表排序
缺点：
- 空间复杂度较高，需要 O(n) 额外空间
- 对于小规模数据，常数因子较大
- 不是原地排序算法

应用场景：

912排序数组
- 问题描述：给你一个整数数组 nums，请你将该数组升序排列。
- 解决方案：归并排序即可
88合并两个有序数组
- 问题描述：请你合并 nums2 到 nums1 中，使合并后的数组同样按 非递减顺序 排列。
- 解决方案：仿照归并排序的思想合并
LCR170交易逆序对的总数
- 问题描述：设计一个程序，输入一段时间内的股票交易记录 record，返回其中存在的「交易逆序对」总数。
- 解决方案：归并排序合并数组过程统计逆序对数量
315计算右侧小于当前元素的个数
- 问题描述：按要求返回一个新数组 counts 。数组 counts 有该性质： counts[i] 的值是 nums[i] 右侧小于 nums[i] 的元素的数量。
- 解决方案：归并过程实际上已经在对逆序对小于数计数了，我们只需要在过程将其记录即可