如何使用递归与分治法进行归并排序

归并排序是一种经典的分治算法，它利用了递归的思想。下面是使用递归和分治法实现归并排序的基本步骤：

1. **分割（Divide）**：首先，我们将原始数组划分为两个相等或接近相等的部分。这通常通过取数组长度的一半完成。

2. **递归（Recursion）**：接着，对这两个子数组分别进行递归调用，执行相同的划分过程，直到每个子数组只剩下一个元素，此时视为排序完成。

3. **合并（Merge）**：当所有子数组都有序后，开始合并过程。从左右两个子数组的首部取出最小值，依次放入新的合并数组，直至其中一个子数组为空，然后将另一个数组剩余部分全部复制到结果数组。

4. **回溯（Combine）**：重复上述合并操作，直到整个数组都合并完毕，这就得到了完全排序的结果。

以下是简单的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 = []
    i = j = 0

    while i < len(left) and j < len(right):
        if left[i] < right[j]:
            merged.append(left[i])
            i += 1
        else:
            merged.append(right[j])
            j += 1

    # 处理未遍历完的部分
    merged.extend(left[i:])
    merged.extend(right[j:])
    
    return merged