归并排序是采用分治思想实现的经典排序算法，核心逻辑是将一个无序数组不断拆分成更小的子数组，直到子数组只剩下一个元素，再将这些有序的子数组逐步合并成最终的有序数组，整个过程分为拆分和合并两个核心阶段。
归并排序的核心原理
归并排序的分治过程可以分为两个明确的步骤：
- 拆分阶段：将长度为n的数组递归拆分成两个长度约为n/2的子数组，直到每个子数组的长度为1，此时单个元素的数组默认是有序的。
- 合并阶段：将两个已经有序的子数组合并成一个新的有序数组，合并时需要比较两个子数组的当前元素，将较小的元素先放入结果数组，直到其中一个子数组被遍历完，再把另一个子数组剩余的元素全部放入结果数组。
Python实现归并排序的完整代码
归并排序的实现需要两个函数，一个是负责拆分数组的递归函数，另一个是负责合并两个有序子数组的函数，具体代码如下：
# 合并两个有序子数组的函数
def merge(left_arr, right_arr):
result = []
i = 0 # 左数组的指针
j = 0 # 右数组的指针
# 比较两个数组的当前元素，将较小的放入结果数组
while i < len(left_arr) and j < len(right_arr):
if left_arr[i] <= right_arr[j]:
result.append(left_arr[i])
i += 1
else:
result.append(right_arr[j])
j += 1
# 将剩余的元素追加到结果数组
if i < len(left_arr):
result.extend(left_arr[i:])
if j < len(right_arr):
result.extend(right_arr[j:])
return result
# 归并排序主函数
def merge_sort(arr):
# 数组长度小于等于1时直接返回，无需排序
if len(arr) <= 1:
return arr
# 找到中间索引，拆分左右子数组
mid = len(arr) // 2
left = merge_sort(arr[:mid])
right = merge_sort(arr[mid:])
# 合并两个有序子数组
return merge(left, right)
# 测试代码
if __name__ == "__main__":
test_arr = [38, 27, 43, 3, 9, 82, 10]
sorted_arr = merge_sort(test_arr)
print("原始数组:", test_arr)
print("排序后数组:", sorted_arr)
代码逻辑解析
上述代码中，merge_sort函数是递归拆分的核心，每次将数组从中间分成两部分，分别递归调用自身处理左右两部分，直到子数组长度为1。之后调用merge函数合并两个有序子数组，合并过程中通过双指针遍历两个子数组，保证合并后的数组依然有序。
测试代码的输出结果如下：
原始数组: [38, 27, 43, 3, 9, 82, 10] 排序后数组: [3, 9, 10, 27, 38, 43, 82]
归并排序的特性分析
时间复杂度
归并排序的时间复杂度在任何情况下都是O(n log n)，因为拆分阶段需要log n层递归，每一层的合并操作总复杂度是O(n)，因此整体复杂度稳定，不会受输入数组有序程度的影响。
空间复杂度
归并排序在合并过程中需要额外的数组存储合并结果，因此空间复杂度为O(n)，相比冒泡排序、插入排序等原地排序算法，空间开销更大。
稳定性
归并排序是稳定的排序算法，在合并两个子数组时，如果左右两个元素相等，优先取左子数组的元素，因此相同元素的相对位置不会改变。
适用场景
归并排序适合处理大规模数据排序，尤其是当数据量较大、对排序稳定性有要求，且可以接受额外空间开销的场景。在Python中，内置的sorted函数和list.sort方法采用的是TimSort算法，它是归并排序和插入排序的结合优化版本，底层也用到了归并排序的核心合并逻辑。