file - 2S-1D vs 2S-2D vs Polyphase 文件排序

Question

有人可以解释一下哪个更好，它们的时间和空间复杂性以及您认为值得了解的任何重要内容的比较。我知道 2S1D 和 2S2D 是如何工作的。

标签： filesortingtime-complexityfile-sorting

Answer 1

我假设“S”表示源，“D”表示目标，因此您正在比较 2 源 1 目标与 2 源 2 目标，以及普通合并排序与多相合并排序。wiki 文章包括以下案例：

https://en.wikipedia.org/wiki/Polyphase_merge_sort

请注意，wiki 文章侧重于外部排序，其中忽略了比较开销，只考虑了数据的移动。

对于具有随机存取存储器的内部普通归并排序，2S-2D 排序只需要两个数组，因为 2 个源可以是偶数和奇数在单个源数组中运行，并且输出也可以是单个数组。对于内部多相归并排序，您至少需要 3 个数组 (2S-1D)。在我的系统上，尽管 3 阵列多相归并排序比 2 阵列普通归并排序多移动约 5%，但多相最终快约 5%，可能是由于缓存问题。

琐事 - 对于 3 堆栈（LIFO 仅接口版本的 2S-1D），多相合并排序是最快的。