045. 编写一个函数，实现归并排序算法

归并排序是一种高效的排序算法，使用分治法（Divide and Conquer）策略将数组分为更小的子数组，然后递归地排序这些子数组，最后将它们合并成一个有序数组。

示例代码

def merge_sort(arr):
    """
    归并排序函数。

    参数:
        arr (list): 输入数组。
    """
    if len(arr) <= 1:
        return arr  # 如果数组长度小于等于1，直接返回数组

    # 找到数组的中间点
    mid = len(arr) // 2

    # 递归地排序左右子数组
    left_half = merge_sort(arr[:mid])
    right_half = merge_sort(arr[mid:])

    # 合并两个有序子数组
    return merge(left_half, right_half)

def merge(left, right):
    """
    合并两个有序数组。

    参数:
        left (list): 左侧有序数组。
        right (list): 右侧有序数组。

    返回:
        list: 合并后的有序数组。
    """
    result = []
    left_index, right_index = 0, 0

    # 合并过程
    while left_index < len(left) and right_index < len(right):
        if left[left_index] < right[right_index]:
            result.append(left[left_index])
            left_index += 1
        else:
            result.append(right[right_index])
            right_index += 1

    # 如果左侧数组还有剩余元素，直接添加到结果中
    result.extend(left[left_index:])

    # 如果右侧数组还有剩余元素，直接添加到结果中
    result.extend(right[right_index:])

    return result

# 测试代码
arr = [3, 6, 8, 10, 1, 2, 1]
print("原始数组：", arr)
sorted_arr = merge_sort(arr)
print("排序后的数组：", sorted_arr)

运行结果

运行上述代码后，输出如下：

原始数组： [3, 6, 8, 10, 1, 2, 1]
排序后的数组： [1, 1, 2, 3, 6, 8, 10]

代码解释

merge_sort 函数：

参数 arr 是输入数组。
如果数组长度小于等于 1，直接返回数组，因为长度为 1 的数组已经是有序的。
找到数组的中间点 mid，将数组分为左右两个子数组。
递归地对左右子数组进行排序。
调用 merge 函数合并两个有序子数组。

merge 函数：

参数 left 和 right 是两个有序数组。
初始化一个空列表 result 用于存储合并后的结果。
使用两个指针 left_index 和 right_index 分别指向两个数组的起始位置。
比较两个数组的当前元素，将较小的元素添加到 result 中，并移动对应的指针。
如果某个数组还有剩余元素，直接将剩余部分添加到 result 中。
返回合并后的有序数组。

注意事项

分治法：归并排序的核心思想是分治法，将大问题分解为小问题，递归地解决小问题，最后将结果合并。

性能：

归并排序的时间复杂度为 O(nlogn)，其中 n 是数组的长度。
归并排序是稳定的排序算法，即相等的元素在排序后保持原来的相对顺序。

空间复杂度：归并排序需要额外的空间来存储临时数组，空间复杂度为 O(n)。

视频讲解

BiliBili： 视睿网络-哔哩哔哩视频 (bilibili.com)