0

我用谷歌搜索了这个主题，所以我找到了一些东西：

Consider a pipeline of sorters S0 to Sm.

S0 has one input stream (the input sequence), and two output streams.
Si (i = 1 to m-1) has two input streams and two output streams. The
output streams of Si are the input streams of Si+1, for i = 0 to m-1.
Sm has two input streams and one output stream.

S0 reads the input stream, creates "sorted" sub-sequences of size one
and sends these intermittently to one of its two output streams.

Si repeatedly reads two sorted sub-sequences, one from each input
stream, merges them, and writes the double sized sorted sub-sequences
intermittently two one of its output streams.

Sm reads two sorted sub-sequences, one from each input stream, merges
these and produces the resulting output sequence.

Here is an example for a sequence of 8 numbers, where a bar | delimits
sorted sub sequences  

                  2 | 1 | 6 | 8  3 1 | 8 4  8 6 5 4 
7 2 3 1 5 6 4 8   ------------>  -------->  ------>   8 7 6 5 4 3 2 1
--------------> S0             S1         S2       S3 -------------->
                  ------------>  -------->  ------>
                  7 | 3 | 5 | 4  7 2 | 6 5  7 3 2 1

我需要一些管道模式中的合并排序伪代码。

4

1 回答 1

1

这看起来是使用“流”的自下而上合并排序（以及此处和此处的讲义）的变体：

自下而上的归并排序是归并排序的一种非递归变体，其中数组按一系列传递进行排序。在每次通过期间，数组被分成大小为 m 的块（最初，m=1）。每两个相邻的块被合并（就像在正常的合并排序中一样），下一次通过两倍大的 m 值。

在 Pipeline Mergesort 中，每个排序器都代表一个通道，因为它组合了相邻的块。但是，与更传统的自底向上合并排序不同，相邻块是从两个输入流中读取的匹配对（而不是在同一流/数组中相邻）。

无论如何，先尝试一下——SO 是一个提出实际问题的地方，而不是发布任务:)

于 2012-10-03T01:28:27.303 回答