python归并排序

归并排序是一种基于分治思想的排序算法，它将一个大的数组分成两个子数组，递归地对这两个子数组进行排序，最后将排好序的子数组合并为一个有序的数组。

下面是 Python 实现归并排序的代码：

def merge_sort(arr):
    if len(arr) > 1:
        mid = len(arr) // 2
        left_arr = arr[:mid]
        right_arr = arr[mid:]

        # 递归地对左右两个子数组进行排序
        merge_sort(left_arr)
        merge_sort(right_arr)

        # 合并两个有序数组
        i = j = k = 0
        while i < len(left_arr) and j < len(right_arr):
            if left_arr[i] < right_arr[j]:
                arr[k] = left_arr[i]
                i += 1
            else:
                arr[k] = right_arr[j]
                j += 1
            k += 1

        # 处理剩余的元素
        while i < len(left_arr):
            arr[k] = left_arr[i]
            i += 1
            k += 1

        while j < len(right_arr):
            arr[k] = right_arr[j]
            j += 1
            k += 1

使用示例：

arr = [38, 27, 43, 3, 9, 82, 10]
merge_sort(arr)
print(arr)  # 输出 [3, 9, 10, 27, 38, 43, 82]

在归并排序中，时间复杂度为 O(nlogn)，空间复杂度为 O(n)。