说我有K个数组A1至AK，长度为L。我想在内存中合并这些数组而不使用太多辅助空间，这样我就具有A1中存在最小的L个元素，A2中最小L的最小L，等等，等等形式的最终输出。基于最小优先级队列的算法需要额外的L*K空间用于输出数组。 L*K约为10亿
您可以在O（n log k）时间和O（1）辅助空间中就地合并总长度为n的k个排序数组。时间复杂度等于使用堆的不适当解决方案。
[Geffert andGajdoš（2010）在文章Multiway in-place merging中描述了该算法：
我们提出了一种渐近有效的k-way合并算法。给定一个数组A包含k个已排序的子序列A_1，...，A_k，其长度分别为n_1，...，n_k，其中Σn_i = n，我们的算法将A_1，...，A_k合并到一个单独的已排序序列中和在线性时间，执行c_k·n + o（n）元素比较，并移动3·n + o（n）元素，其中c_k =⌊lgk⌋+2⋅（1 −2⌊lgk⌋/ k），即满足lg k≤c_k≤⌈lgk⌉的常数，并且以c_k≤lg k + 0.0861为界。该算法不能稳定地合并，但是，它不要求A中的元素都完全不同。