merge sort 如何工作？

Question

merge sort 如何工作？

Accepted Answer

**Merge sort** 是一个**分治**、**稳定**排序算法，运行时间保证为 **O(n log n)**。它将数组分成两半，递归地对每一半进行排序，然后合并两个已排序的一半。

## 核心思想

单个元素已经排序（基本情况）。合并两个有序列表是线性的，而我们执行 log n 层的合并。

## 示例

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

def merge(a, b):
    result, i, j = [], 0, 0
    while i < len(a) and j < len(b):
        if a[i] <= b[j]:              # <= keeps it stable
            result.append(a[i]); i += 1
        else:
            result.append(b[j]); j += 1
    result.extend(a[i:]); result.extend(b[j:])
    return result

merge_sort([5, 2, 4, 1, 3])           # -> [1, 2, 3, 4, 5]
```

## 复杂度

- **Time:** O(n log n) 在所有情况下（最佳、平均、最坏）。
- **Space:** O(n) 用于合并缓冲区（不是原地排序）。

## 何时使用 / 注意事项

当你需要**稳定性**或保证 O(n log n)、以及用于**链表**和**大文件外部排序**时理想。额外的 O(n) 内存是其主要缺点。

## 为什么这很重要

Merge sort 无论输入如何都保证 O(n log n)，不同于 quicksort 的 O(n²) 最坏情况。

其稳定性保留了相等键的相对顺序，这对多键排序很重要。

Merge 步骤是可重用的原语，分治结构是一个模板，你将在各处反复使用。