用python写归并排序

以下是使用Python编写的归并排序算法：

def merge_sort(arr):
    # 如果列表只有一个元素，直接返回
    if len(arr) <= 1:
        return arr
    
    # 将列表分成两半
    mid = len(arr) // 2
    left = arr[:mid]
    right = arr[mid:]
    
    # 对左右两半分别进行归并排序
    left = merge_sort(left)
    right = merge_sort(right)
    
    # 将排序后的左右两半进行合并
    return merge(left, right)

def merge(left, right):
    result = []
    i = 0
    j = 0
    
    # 将左右两个列表中的元素逐个比较，将较小的元素加入结果列表中
    while i < len(left) and j < len(right):
        if left[i] < right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1
    
    # 将剩余的元素加入结果列表中
    result += left[i:]
    result += right[j:]
    
    return result

在这个归并排序算法中，我们使用了递归来将列表分成左右两半，并对左右两半分别进行归并排序。然后，我们使用一个merge()函数将排序后的左右两半进行合并。

merge()函数中，我们使用两个指针i和j来分别指向左右两个列表中的元素，然后逐个比较两个指针指向的元素，将较小的元素加入结果列表中，直到其中一个指针超出了其列表的范围。最后，我们将剩余的元素加入结果列表中，并返回结果列表。