Python函数：如何使用递归和分治法实现归并排序？

归并排序是一种经典的排序算法，使用分治法和递归的思想来排序一个数组。其基本思想是将一个大数组分成两个较小的数组，然后分别对这两个数组进行排序，最后再将排序好的子数组合并起来。

实现归并排序主要包括两个步骤：拆分和合并。

拆分（分治法）：

1. 首先，判断数组的长度是否小于等于1，如果是，则不需要进行排序，直接返回。

2. 如果数组长度大于1，则将数组一分为二，分别递归地对两个子数组进行排序。

合并（递归）：

1. 创建一个用于存放合并后数组的空数组。

2. 使用两个指针，分别指向两个已排序的子数组的起始位置。

3. 比较两个指针所指的元素，将较小的元素放入合并后的数组中，指针后移。

4. 当一个子数组的指针超出范围时，将另一个子数组的剩余元素放入合并后的数组中。

5. 递归地合并两个子数组，直到完成整个数组的排序。

下面是使用递归和分治法实现归并排序的Python代码：

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

def merge(left, right):
    result = []
    i = 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.extend(left[i:])
    result.extend(right[j:])
    return result

在这段代码中，merge_sort函数用于拆分数组，merge函数用于合并两个已排序的子数组。

归并排序的时间复杂度为O(nlogn)，其中n是数组的长度。在拆分阶段，数组被拆分成logn个子问题，而在合并阶段，每个子问题都需要O(n)的时间复杂度，因此总时间复杂度为O(nlogn)。

归并排序是一种稳定的排序算法，适用于各种数据规模的排序需求。