arrays - 合并排序数组，最佳时间复杂度是多少？

Question

我有 m 个数组，每个数组的长度为 n。每个数组都已排序。我想创建一个长度为 m*n 的数组，其中包含已排序的先前数组的所有值(包括重复值)。我必须合并这些数组..

我认为最优的时间复杂度是m*n*log(m)

这是算法的草图..

我创建了一个长度为 m 的支持数组 H，其中包含每个数组第一个元素的所有值。

然后我对该数组进行排序 (m log m)，并将最小值移至输出数组。

然后我将移动的值替换为下一个值，从它被获取的数组中。实际上我并没有替换它，而是将它插入正确(排序)的位置。我认为这需要 log m。

然后我对所有 m*n 值重复此操作...因此 m*n*log m

我的问题.. 你能想到一个更有效的算法吗？如果 mnlogm 实际上是最优的，您至少可以想出一个更简单、更优雅的算法吗？

Answer 1

复杂度是对的!但是，您的算法思想有一个小缺陷:您不能在 log m 中的排序数组中插入一个项目。您可以在这种复杂性中使用二进制搜索找到它的位置，但您可能必须四处移动元素才能将其实际放置在那里。要解决此问题，您可以改用堆数据结构!

多路合并(这是您的算法的通用名称)通常使用另一种“合并”数据结构来实现:锦标赛树。您可以在 Knuth 的“计算机编程艺术”(关于排序的章节，iirc)中找到描述。在这种特定情况下，与堆相比，它在理论上和实践中具有较低的常数因子。

如果您想查看实现，我很确定 GNU C++ 标准库并行扩展中的并行多路合并是通过这种方式实现的。

编辑:我引用了错误的书，现在已修复。