归并排序

归并排序是一种分治算法，将数组分成两半，分别排序后再合并。

概述

归并排序是稳定的排序算法，时间复杂度始终为 O(n log n)。

算法步骤

1. 分割: 将数组分成两半
2. 递归排序: 对每一半进行排序
3. 合并: 将两个已排序的子数组合并

实现

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

# 示例
arr = [38, 27, 43, 3, 9, 82, 10]
sorted_arr = merge_sort(arr)
print(sorted_arr)  # [3, 9, 10, 27, 38, 43, 82]

原地归并排序

def merge_sort_in_place(arr, left, right):
    if left < right:
        mid = (left + right) // 2
        merge_sort_in_place(arr, left, mid)
        merge_sort_in_place(arr, mid + 1, right)
        merge_in_place(arr, left, mid, right)

def merge_in_place(arr, left, mid, right):
    temp = []
    i, j = left, mid + 1
    
    while i <= mid and j <= right:
        if arr[i] <= arr[j]:
            temp.append(arr[i])
            i += 1
        else:
            temp.append(arr[j])
            j += 1
    
    temp.extend(arr[i:mid + 1])
    temp.extend(arr[j:right + 1])
    
    for k in range(left, right + 1):
        arr[k] = temp[k - left]

# 示例
arr = [38, 27, 43, 3, 9, 82, 10]
merge_sort_in_place(arr, 0, len(arr) - 1)
print(arr)  # [3, 9, 10, 27, 38, 43, 82]

复杂度分析

情况	时间复杂度
平均	O(n log n)
最好	O(n log n)
最坏	O(n log n)

空间复杂度

• 标准版本：O(n)
• 原地版本：O(n)（临时数组）

优化策略

迭代版本

def merge_sort_iterative(arr):
    n = len(arr)
    size = 1
    
    while size < n:
        left = 0
        while left < n:
            mid = min(left + size - 1, n - 1)
            right = min(left + 2 * size - 1, n - 1)
            merge_in_place(arr, left, mid, right)
            left += 2 * size
        size *= 2

# 示例
arr = [38, 27, 43, 3, 9, 82, 10]
merge_sort_iterative(arr)
print(arr)  # [3, 9, 10, 27, 38, 43, 82]

自然归并排序

def natural_merge_sort(arr):
    runs = find_runs(arr)
    
    while len(runs) > 1:
        new_runs = []
        i = 0
        while i < len(runs):
            if i + 1 < len(runs):
                merged = merge(runs[i], runs[i + 1])
                new_runs.append(merged)
                i += 2
            else:
                new_runs.append(runs[i])
                i += 1
        runs = new_runs
    
    return runs[0] if runs else []

def find_runs(arr):
    runs = []
    if not arr:
        return runs
    
    current_run = [arr[0]]
    for i in range(1, len(arr)):
        if arr[i] >= arr[i - 1]:
            current_run.append(arr[i])
        else:
            runs.append(current_run)
            current_run = [arr[i]]
    runs.append(current_run)
    
    return runs

应用场景

• 需要稳定排序的场景
• 外部排序（处理大数据集）
• 链表排序

与其他排序算法对比

算法	平均时间	空间	稳定
归并排序	O(n log n)	O(n)	是
快速排序	O(n log n)	O(log n)	否
堆排序	O(n log n)	O(1)	否