使用分制法实现对无序数组的排序

在计算机科学中，分治算法（Divide and Conquer）通常用于排序，其中一种常见的应用就是归并排序（Merge Sort）。分治法的基本思想是将一个大问题分解成两个或更多个相同规模的小问题，然后递归地解决这些小问题，最后合并解决方案得到原问题的答案。

对于无序数组的排序，归并排序就是一个很好的例子：

1. 分治过程：
- **分割**（Divide）：将数组一分为二，直到每个子数组只剩下一个元素，此时视为已经排序。
- **解决**（Conquer）：对于每个子数组，我们不需要做任何操作，因为只有一个元素的数组默认是有序的。
- **合并**（Combine）：将已排序的两个子数组合并成一个大的、已排序的数组。这通常是通过比较元素并将它们按顺序放入新数组中完成的。

2. 归并排序算法步骤：
- 递归调用：将原始数组分成两半，分别对左右半部分进行排序。
- 合并过程：创建一个新的空数组，从两个已排序数组的起始位置开始，比较当前元素，较小的添加到结果数组，重复此过程直到其中一个数组遍历完，再将另一个数组剩余的部分全部添加到结果数组。
- 返回：当所有元素都添加到结果数组后，整个排序过程结束，返回这个已排序的新数组。

这是一个基本的伪代码示例：

def merge_sort(arr):
    if len(arr) <= 1:
        return arr  # 如果长度为1，直接返回

    mid = len(arr) // 2
    left_half = merge_sort(arr[:mid])
    right_half = merge_sort(arr[mid:])

    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