归并排序（Merge Sort）

# /*
# 归并排序（Merge Sort）
# --------------------------------------------------------
# 原理：
# 采用典型的“分而治之”策略。
# 将序列不断二分，直到无法再分（每段只有 1 个元素），
# 再将多个有序小段按顺序合并，最终形成完整的有序序列。
#
# 归并排序的稳定性与可预测的 O(n log n) 性能，
# 使其成为非常经典且可靠的排序方法。
# */

# 合并两个有序列表
def merge(left, right):
    result = []
    i = j = 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


# 主函数：归并排序
def merge_sort(arr):
    if len(arr) <= 1:      # 长度 0 或 1，自然有序
        return arr

    mid = len(arr) // 2
    left = merge_sort(arr[:mid])     # 排序左部分
    right = merge_sort(arr[mid:])    # 排序右部分

    return merge(left, right)        # 合并左右有序序列


# 示例演示
data = [12, 11, 13, 5, 6, 7]
print("排序前：", data)
result = merge_sort(data)
print("排序后：", result)

# --------------------------------------------------------
# 关键要点总结：
# 1) 分治思想：先分后合；
# 2) 合并时保持原相对顺序，因此是“稳定排序”；
# 3) 时间复杂度稳定为 O(n log n)，不受数据分布影响；
# 4) 需要额外空间存放合并结果，空间复杂度 O(n)；
# 5) 在处理大规模数据时非常高效，性能可预测。
# */

#
# 排序前： [12, 11, 13, 5, 6, 7]
# 排序后： [5, 6, 7, 11, 12, 13]