用python实现归并排序

以下是Python实现归并排序的代码和解释：

def merge_sort(arr):
    if len(arr) > 1:
        mid = len(arr) // 2  # 找到中间位置
        left_half = arr[:mid]  # 将列表分为左右两半
        right_half = arr[mid:]

        merge_sort(left_half)  # 递归调用merge_sort()函数
        merge_sort(right_half)

        i = j = k = 0  # 初始化三个指针

        # 将左右两个有序列表合并成一个有序列表
        while i < len(left_half) and j < len(right_half):
            if left_half[i] < right_half[j]:
                arr[k] = left_half[i]
                i += 1
            else:
                arr[k] = right_half[j]
                j += 1
            k += 1

        # 将剩余的元素添加到列表末尾
        while i < len(left_half):
            arr[k] = left_half[i]
            i += 1
            k += 1

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

# 测试代码
arr = [64, 34, 25, 12, 22, 11, 90]
merge_sort(arr)
print("排序后的列表：", arr)

输出结果为：`排序后的列表： [11, 12, 22, 25, 34, 64, 90]`

代码解释：

1. `merge_sort()`函数接收一个列表作为参数，如果列表长度大于1，则将列表分为左右两半，然后递归调用`merge_sort()`函数对左右两个子列表进行排序。
2. `merge()`函数用于将两个有序列表合并成一个有序列表。在`merge_sort()`函数中，当左右两个子列表都排好序后，调用`merge()`函数将它们合并成一个有序列表。
3. 在`merge()`函数中，使用三个指针`i`、`j`、`k`分别指向左右两个子列表和合并后的列表。比较左右两个子列表的元素大小，将较小的元素添加到合并后的列表中，并将指针向后移动一位。当其中一个子列表的元素全部添加到合并后的列表中后，将另一个子列表的剩余元素添加到列表末尾。