algorithm - 是否有一些有效的算法可以在 O(1) 额外空间或最小额外空间中合并 k 个排序数组

Question

假设我有 K 个长度为 L 的数组 A1 到 AK 。我想在不使用太多辅助空间的情况下在内存中合并这些数组，以便我得到形式为 的最终输出最小的 L 个元素出现在 A1 中，其次是 A2 中最小的 L，依此类推 .基于最小优先级队列的算法需要额外的 L*K输出数组的空间。 L*K大约是 10 亿

Answer 1

您可以在 O(n log k) 时间和 O(1) 辅助空间中就地合并 k 个总长度为 n 的排序数组。时间复杂度等于使用堆的异地解决方案。

该算法在文章 Multiway in-place merging 中有所描述。作者 Geffert 和 Gajdoš (2010):

We present an algorithm for asymptotically efficient k-way merging. Given an array A containing k sorted subsequences A_1, ..., A_k of respective lengths n_1, ..., n_k, where Σ n_i = n, our algorithm merges A_1, ..., A_k into a single sorted sequence in-place and in linear time, performing c_k·n + o(n) element comparisons and 3·n + o(n) element moves, where c_k = ⌊lg k⌋ + 2⋅(1 − 2⌊lg k⌋/k), which is a constant satisfying lg k ≤ c_k ≤ ⌈lg k⌉ and, moreover, bounded by c_k ≤ lg k + 0.0861. The algorithm does not merge stably, however, it does not require that the elements in A are all distinct.