如何使用MERGE SORT对K个已排序的数组进行排序

Question

我知道这个问题已被提出,并且使用最小堆有一个非常好的优雅解决方案.

我的问题是如何使用合并排序的合并功能来做到这一点.

您已经有一组已排序的数组.所以你应该能够在O(nlog K)时间将它们合并到一个数组中,对吗？

我只是想不通怎么做!

说我有

[[5,6],[3,4],[1,2],[0]]

第1步:[[3,4,5,6],[0,1,2]]

第2步:[[0,1,2,3,4,5,6]]

有一个简单的方法吗？O(nlog K)理论上是否可以通过mergesort实现？

Answer 1

正如其他人所说,使用最小堆来保存下一个项目是最佳方式.它被称为N路合并.其复杂度为O(n log k).

您可以使用双向合并算法对k阵列进行排序.也许最简单的方法是修改标准合并排序,以便它使用非常量分区大小.例如,假设您有4个长度为10,8,12和33的数组.每个数组都已排序.如果将数组连接成一个,则会有这些分区(数字是数组的索引,而不是值):

[0-9][10-17][18-29][30-62]

合并排序的第一次传递将具有0和10的起始索引.您可以将其合并到新数组中,就像使用标准合并排序一样.下一遍将从第二个阵列中的位置18和30开始.完成第二遍后,输出数组包含:

[0-17][18-62]

现在你的分区从0和18开始.你将这两个合并到一个数组中就完成了.

唯一真正的区别是,不是以分区大小2和加倍开始,而是具有非常量分区大小.在进行每次传递时,新分区大小是您在上一次传递中使用的两个分区的大小之和.这实际上只是对标准合并排序的略微修改.

它将通过log(k)传递来进行排序,并在每次传递时查看所有n个项目.该算法为O(n log k),但具有比N路合并高得多的常数.

对于实现,构建一个包含每个子数组的起始索引的整数数组.所以在上面的例子中你会得到:

int[] partitions = [0, 10, 18, 30];
int numPartitions = 4;

现在,您进行标准合并排序.但是您从partitions阵列中选择分区.所以你的合并将从以下开始:

merge (inputArray, outputArray, part1Index, part2Index, outputStart)
{
    part1Start = partitions[part1Index];
    part2Start = partitions[part2Index];

    part1Length = part2Start - part1Start;
    part2Length = partitions[part2Index-1] - part2Start;

    // now merge part1 and part2 into the output array,
    // starting at outputStart
}

你的主循环看起来像:

while (numPartitions > 1)
{
    for (int p = 0; p < numPartitions; p += 2)
    {
        outputStart = partitions[p];
        merge(inputArray, outputArray, p, p+1, outputStart);
        // update partitions table
        partitions[p/2] = partitions[p] + partitions[p+1];
    }
    numPartitions /= 2;
}

这是基本的想法.当数字是奇数时,你将不得不做一些工作来处理悬空分区,但总的来说,它是如何完成的.

您也可以通过维护一个数组数组,并将每两个数组合并为一个新数组,并将其添加到数组的输出数组中来实现.泡沫,冲洗,重复.

Answer 2

您应该注意,当我们说复杂度为O(n log k)时,我们假设n表示所有k个数组中的元素的TOTAL数,即最终合并数组中的元素数.

例如,如果要合并每个包含n个元素的k个数组,则最终数组中的元素总数将为nk.所以复杂性将是O(nk log k).