python编写归并排序

归并排序是一种基于分治思想的排序算法，它将待排序的数组分为两个子数组，对每个子数组进行递归地排序，然后将两个已经有序的子数组合并成一个有序的数组。

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

def merge_sort(arr):
    if len(arr) <= 1:
        return arr
    mid = len(arr) // 2
    left_arr = merge_sort(arr[:mid])
    right_arr = merge_sort(arr[mid:])
    return merge(left_arr, right_arr)

def merge(left_arr, right_arr):
    result = []
    i, j = 0, 0
    while i < len(left_arr) and j < len(right_arr):
        if left_arr[i] <= right_arr[j]:
            result.append(left_arr[i])
            i += 1
        else:
            result.append(right_arr[j])
            j += 1
    result += left_arr[i:]
    result += right_arr[j:]
    return result

在上述代码中，merge_sort()函数是归并排序的入口函数，它接受一个待排序的数组作为输入参数，并返回一个排好序的新数组。在该函数中，如果数组的长度小于等于1，则直接返回该数组；否则，将该数组分为两个子数组，对每个子数组进行递归排序，然后将排序后的子数组合并为一个有序的数组。

merge()函数是实现两个有序数组合并的核心函数。在该函数中，使用i和j两个指针分别指向左右两个有序数组的头部，比较两个指针所指向的元素大小，将较小的元素添加到结果数组中，并移动指针。最后将剩余的元素添加到结果数组中即可。