归并排序图解

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

# 测试归并排序
if __name__ == "__main__":
    arr = [38, 27, 43, 3, 9, 82, 10]
    print("原始数组:", arr)
    sorted_arr = merge_sort(arr)
    print("排序后数组:", sorted_arr)

归并排序是一种经典的分治算法，通过递归地将数组分解为更小的部分，然后合并排序后的结果来实现高效排序。它的主要优势在于：

• 稳定的 O(n log n) 时间复杂度，适用于大规模数据集
• 稳定的排序算法，保持相等元素的原始顺序
• 可用于外部排序和链表排序等特殊场景

尽管需要额外的存储空间，归并排序仍然是许多编程语言标准库中排序函数的实现基础（如Python的sorted()和Java的Arrays.sort()）。掌握归并排序不仅有助于理解分治算法思想，也是学习更高级算法的基础。