归并排序

"""
归并排序
"""
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, 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   

arr = [64, 34, 25, 12, 22, 11, 90]
sorted_arr = merge_sort(arr)
print(sorted_arr)

下面为你详细解释这段Python代码的含义、实现原理、用途以及注意事项。

### 一、 代码含义

这段代码实现的是经典的排序算法——**归并排序**。它将一个无序的数组 [64, 34, 25, 12, 22, 11, 90] 通过归并排序算法，最终输出有序的数组 [11, 12, 22, 25, 34, 64, 90]。

### 二、 实现原理

归并排序的核心思想是**“分而治之”**。整个过程分为两个阶段：**分解**和**合并**。

1. **分解阶段merge_sort 函数）：**

- **递归终止条件**：如果数组的长度小于等于1，说明数组已经是有序的，直接返回该数组。

- **拆分数组**：找到数组的中间位置 mid，将数组从中间一分为二，分为左半部分 left 和右半部分 right。

- **递归调用**：对左半部分和右半部分分别继续调用 merge_sort 函数，直到所有的子数组长度都为1。

2. **合并阶段merge 函数）：**

- 创建一个空数组 result 用于存放合并后的结果。

- 使用两个指针 i 和 j，分别指向左子数组 left 和右子数组 right 的起始位置。

- 比较 left[i] 和 right[j]：

- 如果左边的元素更小，将其追加到 result 中，并将指针 i 右移一位i += 1）。

- 否则，将右边的元素追加到 result 中，并将指针 j 右移一位j += 1）。

- 循环结束的条件是其中一个数组的元素全部被加入到了 result 中。

- 最后，将未遍历完的数组剩余部分直接拼接到 result 的末尾（因为剩余部分本身已经是排好序的）。

- 返回合并后的有序数组。

### 三、 用途

1. **大规模数据排序**：归并排序的时间复杂度稳定为 $O(n \log n)$，非常适合处理大量数据的排序。

2. **外部排序**：当数据量太大，无法全部加载到内存中时，归并排序是外部排序的基础。可以将大数据切分成小块分别排序后，再通过多路归并合并。

3. **链表排序**：相比于快速排序，归并排序不需要随机访问数据，因此它是排序链表的首选算法。

4. **稳定排序需求**：归并排序是**稳定排序**（即如果两个元素值相等，排序后它们的相对顺序保持不变），在需要保持原有相对顺序的场景下非常有用。

### 四、 注意事项

1. **空间复杂度较高**：

- 归并排序不是原地排序，在合并过程中需要额外的内存空间。在上述代码中，由于使用了切片 arr[:mid] 和 result.extend()，每次递归都会创建新的列表，空间复杂度为 $O(n \log n)$。

- **优化建议**：如果对内存有严格要求，可以只开辟一个大小为 $n$ 的辅助数组，在原数组上进行索引操作和合并，这样空间复杂度可以降至 $O(n)$。

2. **Python切片的额外开销**：

- 代码中的 arr[:mid] 和 arr[mid:] 会产生列表的浅拷贝，这在Python中虽然写法简洁，但会增加时间和空间的消耗，尤其是在递归深处。

3. **小数组效率问题**：

- 对于非常小的数组（如长度小于15），归并排序的递归开销反而比插入排序等简单算法要大。在实际工程应用中（如Python内置的TimSort），通常会在小规模数据时切换为插入排序。

4. **原地修改问题**：

- 这段代码返回的是一个**新**的排好序的列表，并没有修改原始的 arr 列表。如果你希望直接在原列表上修改，需要调整代码逻辑或使用 arr[:] = merge_sort(arr) 的方式。

希望这个解释对你理解归并排序有所帮助！如果你还有其他关于代码的问题，随时可以问我。