正如其他人所说，使用最小堆来容纳下一个项目是最佳方法。这称为N路合并。它的复杂度为O（n log k）。

您 可以
使用2向合并算法对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;
}

这是基本思想。当数字为奇数时，您将不得不做一些工作来处理悬空的分区，但总的来说就是这样。

您还可以通过维护一个数组数组，并将每两个数组合并到一个新数组中，然后将其添加到数组的输出数组中，来完成此操作。泡沫，冲洗，重复。