🧠 算法简介

合并排序是一种分治法实现的稳定排序算法，时间复杂度为 O(n log n)。其核心思想是将数组分为两半，分别排序后再合并。

merge_sort_process

✅ Python 实现代码

def merge_sort(arr):
    """合并排序算法实现"""
    if len(arr) > 1:
        mid = len(arr) // 2
        left = arr[:mid]
        right = arr[mid:]
        
        # 递归排序左右子数组
        merge_sort(left)
        merge_sort(right)
        
        # 合并有序子数组
        i = j = k = 0
        while i < len(left) and j < len(right):
            if left[i] < right[j]:
                arr[k] = left[i]
                i += 1
            else:
                arr[k] = right[j]
                j += 1
            k += 1
        
        # 处理剩余元素
        while i < len(left):
            arr[k] = left[i]
            i += 1
            k += 1
        while j < len(right):
            arr[k] = right[j]
            j += 1
            k += 1
    return arr

# 示例用法
if __name__ == "__main__":
    nums = [38, 27, 43, 3, 9, 82, 10]
    print("原始数组:", nums)
    print("排序结果:", merge_sort(nums))

📚 相关扩展阅读

⚠️ 注意事项

  1. 合并排序需要额外 O(n) 空间复杂度
  2. 适合用于链表结构排序（数组实现时需注意内存分配）
  3. 是稳定排序算法，适合需要保持相同元素相对顺序的场景
merge_sort_steps