Python 归并排序实现的算法？

归并排序是一种有效的排序算法，它的基本思想是分解待排序的序列，然后合并它们。具体来说，归并排序首先将待排序的序列分解为两个等长（几乎等长）的子序列，然后对子序列进行排序，最后将排序结果合并起来。

以下是一个使用 Python 实现的归并排序算法：

def merge_sort(arr):
    if len(arr) <= 1:
        return arr

    # 找到中点，将数组分解为两个子数组
    mid = len(arr) // 2
    left_half = arr[:mid]
    right_half = arr[mid:]

    # 递归地对子数组进行排序
    left_half = merge_sort(left_half)
    right_half = merge_sort(right_half)

    # 合并排序后的子数组
    return merge(left_half, right_half)

def merge(left, right):
    merged = []
    left_index = 0
    right_index = 0

    # 比较两个子数组的元素，将较小的元素添加到结果数组中
    while left_index < len(left) and right_index < len(right):
        if left[left_index] < right[right_index]:
            merged.append(left[left_index])
            left_index += 1
        else:
            merged.append(right[right_index])
            right_index += 1

    # 如果左子数组还有剩余元素，将它们添加到结果数组中
    while left_index < len(left):
        merged.append(left[left_index])
        left_index += 1

    # 如果右子数组还有剩余元素，将它们添加到结果数组中
    while right_index < len(right):
        merged.append(right[right_index])
        right_index += 1

    return merged

在这个实现中，merge_sort 函数首先检查输入数组的长度。如果长度小于或等于 1，那么数组已经是有序的，可以直接返回。否则，它找到数组的中点，并将数组分解为两个子数组。然后，它递归地对子数组进行排序，并使用 merge 函数将排序后的子数组合并为一个有序数组。

merge 函数创建了一个新的空数组，并使用两个索引来追踪左子数组和右子数组中的元素。它比较两个子数组中的元素，并将较小的元素添加到结果数组中。当其中一个子数组的所有元素都被添加到结果数组中时，它将另一个子数组的剩余元素添加到结果数组中。最后，它返回排序后的结果数组。