设计自顶向下的二路归并排序算法

设计自顶向下的二路归并排序算法通常采用分治策略，适用于大规模数据的有序排列。下面是该算法的基本步骤：

1. **分解**（Divide）: 将原始数组一分为二，直到每个子序列只有一个元素。这个过程称为“划分”阶段。

2. **解决**（Conquer）: 对每个子序列分别进行排序。对于单个元素的子序列，它们本身就是有序的，所以不需要进一步处理。

3. **合并**（Combine）: 当两个已排序的子序列相遇时，将它们合并成一个新的有序序列。这一步通过比较两个子序列的当前元素，选择较小的一个放入结果数组，并移动指针到下一个未处理的元素。

4. **回溯**（Combine Backward）: 重复合并操作，直到所有的子序列都被合并成最终的有序数组。

以下是递归实现的伪代码示例：

def merge_sort(arr):
    if len(arr) <= 1:  # 如果子数组只剩一个元素或为空，返回数组本身
        return arr

    mid = len(arr) // 2
    left_half = arr[:mid]  # 左半部分
    right_half = arr[mid:]  # 右半部分

    # 递归对左右两部分进行排序
    left_sorted = merge_sort(left_half)
    right_sorted = merge_sort(right_half)

    # 合并两个有序数组
    sorted_arr = merge(left_sorted, right_sorted)
    return sorted_arr

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