用python写一个归并排序

归并排序是一种分治算法，它将一个大问题拆分成若干个小问题，然后将小问题的结果合并起来得到大问题的解。具体实现过程如下：

1. 将待排序数组拆分成左右两个子数组，直到子数组只有一个元素为止。
2. 对左右两个子数组分别进行归并排序，递归调用归并排序函数。
3. 将左右两个排序后的子数组合并成一个有序数组。

下面是使用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
    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两个指针分别指向左右两个数组的头部，比较两个指针所指元素的大小，将较小的元素加入到结果数组中，然后将指针右移一位。最后将剩余的元素加入到结果数组中，返回结果数组。

我们可以使用以下代码来测试归并排序的效果：

arr = [3, 5, 1, 4, 2, 6]
sorted_arr = merge_sort(arr)
print(sorted_arr)
# 输出：[1, 2, 3, 4, 5, 6]

以上代码将一个无序数组排序后输出。