归并排序第二部分实现咨询：合并已排序子数组并排序

你需要实现的是归并排序的合并阶段——将多个已排序的子数组合并为一个整体有序的数组，以下是两种贴合归并排序原理的实现方案：

方法一：两两迭代合并（最贴合归并排序原始逻辑） #

归并排序的核心合并逻辑就是先将两个有序数组合并为一个有序数组，我们可以把这个逻辑扩展为依次合并所有子数组：

1. 先合并前两个子数组，得到一个新的有序数组
2. 将这个新数组与下一个子数组合并，重复此过程直到所有子数组完成合并

代码实现（Python） #

def merge_two_sorted_arrays(a, b):
    merged = []
    i = j = 0
    # 双指针遍历，每次取两个数组中较小的元素加入结果
    while i < len(a) and j < len(b):
        if a[i] < b[j]:
            merged.append(a[i])
            i += 1
        else:
            merged.append(b[j])
            j += 1
    # 处理剩余未遍历完的元素
    merged.extend(a[i:])
    merged.extend(b[j:])
    return merged

def merge_multiple_sorted_arrays(arrays):
    if not arrays:
        return []
    result = arrays[0]
    # 依次合并后续每个子数组
    for arr in arrays[1:]:
        result = merge_two_sorted_arrays(result, arr)
    return result

# 测试用例
input_arrays = [[1,2],[4,5],[2,3],[5,8]]
print(merge_multiple_sorted_arrays(input_arrays))  # 输出: [1, 2, 2, 3, 4, 5, 5, 8]

特点：逻辑直观，完全遵循归并排序的合并流程，但当子数组数量较多时，时间效率会降低（总时间复杂度为O(n*k)，n为子数组数量，k为子数组平均长度）。

方法二：小顶堆优化合并（适合大量子数组场景） #

如果子数组数量较多，两两合并的效率不足，可以用小顶堆来同时跟踪所有子数组的当前最小元素，每次取出堆顶的最小元素后，将对应子数组的下一个元素加入堆中，直到所有元素处理完毕。

代码实现（Python） #

import heapq

def merge_multiple_sorted_arrays_heap(arrays):
    heap = []
    # 初始化堆：存储(当前元素值, 子数组索引, 元素在子数组中的位置)
    for idx, arr in enumerate(arrays):
        if arr:  # 跳过空的子数组
            heapq.heappush(heap, (arr[0], idx, 0))
    
    merged = []
    while heap:
        val, arr_idx, elem_idx = heapq.heappop(heap)
        merged.append(val)
        # 如果当前子数组还有未处理的元素，将下一个元素加入堆
        if elem_idx + 1 < len(arrays[arr_idx]):
            next_val = arrays[arr_idx][elem_idx + 1]
            heapq.heappush(heap, (next_val, arr_idx, elem_idx + 1))
    return merged

# 测试用例
input_arrays = [[1,2],[4,5],[2,3],[5,8]]
print(merge_multiple_sorted_arrays_heap(input_arrays))  # 输出: [1, 2, 2, 3, 4, 5, 5, 8]

特点：时间效率更高，总时间复杂度为O(m log n)（m为所有元素的总数量，n为子数组数量），适合子数组数量多、总元素量大的场景。

内容的提问来源于stack exchange，提问作者Kajstrl