前言
归并排序（Merge Sort）较早为通用存储程序计算机设计的算法之一。它由冯·诺依曼（John von Neumann）在 1945 年发表的“101 报告”时提出，后于 1951 年完成的 EDVAC 计算机上应用了这一算法。
基本思想
将一个数组不断地分成两半，分别对这两半进行排序，然后将排序好的两半合并起来。
复杂度
一种稳定的排序算法，即相同元素的相对顺序在排序前后不会改变。
时间复杂度 O(nlogn)
空间复杂度 O(n)
一般步骤
- 分解：将待排序的数组不断地“一分为二”，直到每个子数组只包含一个元素。
- 递归排序与合并：在分解过程完成后，递归地对每个子数组进行排序，并将两个相邻的已排序子数组合并成一个有序的新数组。合并时，通过比较两个子数组的元素，按顺序放入新数组中。
- 结束条件：当所有子数组都合并完毕，最终得到的数组就是完全有序的。
应用场景
归并排序由于其稳定、高效的特点。
只要涉及到对大量数据进行排序且对稳定性有要求的场景，归并排序都可能是一个合适的选择。
- 大规模数据排序：当需要对大量数据进行排序时，归并排序的 时间复杂度能够保证较好的性能。
- 外部排序：当数据量太大而无法一次性放入内存时，归并排序常用于外部排序算法中。可以将数据分成多个较小的块，在内存中对每个块进行排序，然后逐步将这些已排序的块合并。
- 分布式系统：在分布式计算环境中，数据可能分布在不同的节点上。归并排序的思想可以用于合并来自不同节点的已排序数据段。
- 数据库操作：数据库在对大型数据表进行排序或合并操作时，可能会使用类似归并排序的策略。
- 排序算法比较和教学：由于归并排序具有清晰的分治思想和相对简单的实现逻辑，常被用于算法教学和不同排序算法的性能比较。
- 多路归并：在处理多个已排序的数据流（如文件）并将它们合并为一个有序数据流的情况下，归并排序的思想可以扩展为多路归并。
代码
def merge_sort(arr):
if len(arr) <= 1:
return arr
mid = len(arr) // 2
left_half = merge_sort(arr[:mid])
right_half = merge_sort(arr[mid:])
return merge(left_half, right_half)
def merge(left, right):
result = []
left_index = 0
right_index = 0
while left_index < len(left) and right_index < len(right):
if left[left_index] < right[right_index]:
result.append(left[left_index])
left_index += 1
else:
result.append(right[right_index])
right_index += 1
result.extend(left[left_index:])
result.extend(right[right_index:])
return result运行样例
array_A = [5, 2, 4, 7, 1, 3, 4, 6]
array_B = merge_sort(array_A)
print(array_B)
# [1, 2, 3, 4, 4, 5, 6, 7]
