🧮 归并排序 (Merge Sort)

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

📖 算法简介 / Introduction

归并排序是采用分治策略的稳定排序算法，将数组递归分成小数组，排序后合并。

Merge sort is a stable sorting algorithm using divide-and-conquer, splitting arrays recursively, sorting, then merging.

💡 算法原理 / Principle

递归地将数组分成两半，分别排序后合并成一个有序数组。

Recursively split the array into two halves, sort each half, then merge them into a single sorted array.

📝 代码实现 / 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] 排序后为 [3, 9, 10, 27, 38, 43, 82]。

Array [38, 27, 43, 3, 9, 82, 10] becomes [3, 9, 10, 27, 38, 43, 82] after sorting.

🎯 适用场景 / Scenarios

外部排序, 链表排序, 需要稳定排序

External sorting, Linked list sorting, Requiring stable sorting

🔄 扩展阅读 / Further Reading

• 建议在 LeetCode 或 HackerRank 上刷相关题目
• 尝试自己实现非递归版本
• 对比其他同类型算法的性能差异