归并排序

归并排序是一种基于分治思想的高效排序算法，核心思路是把一个大问题拆解成多个小问题，先解决小问题，再把小问题的结果合并，最终得到完整答案。

注意：并归排序是稳定排序（相等元素的相对顺序不变）、非原地排序（需要额外空间存储数据），时间效率非常高。

归并排序严格遵循分 → 治 → 合的流程：

（1）分（Divide）：把待排序的数组从中间分成左右两个子数组，递归拆分，直到每个子数组只有 1 个元素（单个元素天然有序）。

（2）治（Conquer）：递归地对拆分后的左右两个子数组分别进行归并排序。

（3）合（Merge）：将两个已经排好序的子数组合并成一个有序数组，这是归并排序的核心步骤。

举个直观例子，请对数组 [38, 27, 43, 3, 9, 82, 10] 排序，过程如下：

（1）拆分，持续拆分到单个元素，即数组的长度为 1。

（2）合并：两两合并有序小数组，最终得到完整有序数组。

示例代码：

def merge(left_arr, right_arr):
    """
    核心：合并两个已经有序的数组
    :param left_arr: 左有序数组
    :param right_arr: 右有序数组
    :return: 合并后的完整有序数组
    """
    result = []  # 临时数组存储合并结果
    i = j = 0  # 双指针，分别遍历左右数组

    # 双指针比较两个数组元素，按顺序加入结果
    while i < len(left_arr) and j < len(right_arr):
        if left_arr[i] <= right_arr[j]:
            result.append(left_arr[i])
            i += 1
        else:
            result.append(right_arr[j])
            j += 1

    # 把剩余未遍历完的元素直接追加到结果（剩余部分本身有序）
    result += left_arr[i:]
    result += right_arr[j:]

    return result


def merge_sort(arr):
    """
    归并排序主函数：递归拆分 + 合并
    :param arr: 待排序数组
    :return: 排序后的数组
    """
    # 递归终止条件：数组长度<=1，天然有序，直接返回
    if len(arr) <= 1:
        return arr

    # 分：从中间拆分数组
    mid = len(arr) // 2
    # 递归排序左半部分
    left = merge_sort(arr[:mid])
    # 递归排序右半部分
    right = merge_sort(arr[mid:])

    # 合：合并两个有序数组
    return merge(left, right)


if __name__ == '__main__':
    test_arr = [38, 27, 43, 3, 9, 82, 10]
    print("原始数组：", test_arr)
    sorted_arr = merge_sort(test_arr)
    print("排序后：", sorted_arr)

运行结果：

原始数组： [38, 27, 43, 3, 9, 82, 10]
排序后： [3, 9, 10, 27, 38, 43, 82]