🧮 归并排序 (Merge Sort)

难度 / Difficulty: 中等 (Medium)
分类 / Category: 排序 (Sorting)
时间复杂度 / Time Complexity: O(n log n)
空间复杂度 / Space Complexity: O(n)

📖 算法简介 / Introduction

归并排序是采用分治策略的稳定排序算法，将数组递归分成小数组，排序后合并。稳定性是其最大优势——相等的元素不会被交换位置。

归并排序的核心思想：分而治之。将数组不断拆分到只剩一个元素，然后两两合并排序。

💡 算法原理 / Principle

1. 分解：将数组从中间分成两半，递归分解直到每部分只有一个元素
2. 解决：对每对分离的数组进行排序（一个元素天然有序）
3. 合并：将两个有序数组合并成一个有序数组

递归公式：T(n) = 2T(n/2) + O(n) → 推导得 O(n log n)

📝 代码实现 / Implementation

def merge_sort(arr):
    if len(arr) <= 1:
        return arr
    mid = len(arr) // 2
    left = merge_sort(arr[:mid])
    right = merge_sort(arr[mid:])
    return merge(left, right)

def merge(left, right):
    result = []
    i = j = 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1
    result.extend(left[i:])
    result.extend(right[j:])
    return result

✨ 示例 / Example

数组 [38, 27, 43, 3, 9, 82, 10] 排序过程：

分解：[38, 27, 43, 3] | [9, 82, 10]
分解：[38, 27] | [43, 3] | [9, 82] | [10]
分解：[38] | [27] | [43] | [3] | [9] | [82] | [10]
合并：[27, 38] | [3, 43] | [9, 82] | [10]
合并：[3, 27, 38, 43] | [9, 10, 82]
合并：[3, 9, 10, 27, 38, 43, 82]

最终结果：[3, 9, 10, 27, 38, 43, 82]

🎯 适用场景 / Scenarios

• 外部排序（大数据量）
• 链表排序
• 需要稳定排序的场景
• 并行计算（天然可并行）

🔄 扩展阅读 / Further Reading

• 对比快速排序：快速排序原地排序（O(1)空间），归并排序需要额外空间
• 优化：对于小数组使用插入排序，减少递归开销