2. 设计分治法实现二路归并排序。 利用递归思想，实现自上向下的二路归并排序。

二路归并排序是一种采用分治策略的排序算法，它将待排序数组分成两个独立的子序列，分别对这两个子序列进行排序，然后合并它们。下面是设计分治法实现二路归并排序的基本步骤：

1. **划分** (Divide): 首先将输入数组分为两个相等的子数组。这通常通过选择数组中间位置来进行，把元素一分为二。

2. **排序** (Conquer): 对每个子数组递归地应用同样的过程，直到子数组只有一个元素或者为空，此时数组已自然排序。

3. **合并** (Combine): 当两个有序子数组处理完毕后，开始合并。创建一个新的临时数组，并从两个子数组的起始位置开始比较元素，较小的元素放入临时数组，同时移动对应的指针。重复这个过程，直到其中一个子数组完全遍历完，再将另一个子数组剩余的部分直接复制到临时数组中。

4. **回溯** (Recursion): 当所有的元素都合并到临时数组后，返回上一层，继续处理下一个子数组，直至原数组完全排序。

以下是简单的伪代码示例：

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)

    # 合并
    sorted_arr = merge(left_half, right_half)
    return sorted_arr

def merge(left, right):
    merged = []
    i, j = 0, 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

# 示例
arr = [5, 2, 9, 1, 5, 6]
sorted_arr = merge_sort(arr)