归并排序 (Merge Sort)

概述

难度：中等 (Medium)
分类：Sorting / 排序

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

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

算法原理

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

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

复杂度分析

代码实现

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

每日练习

1. 完成算法实现
2. 分析算法复杂度
3. 思考：算法的适用场景和局限性

相关阅读：算法专栏

💡 学习建议：算法学习重在理解思想，多写多练是关键。 💡 Learning tip: Algorithm learning is about understanding the core idea. Practice makes perfect.