Java 中的管道合并排序

Question

>我谷歌这个话题，所以我找到了一些东西：

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 

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

Answer 1

这

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

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

在管道合并排序

中，每个排序器在合并相邻块时表示一个通道。但是，与更传统的自下而上的合并排序不同，相邻块是从两个输入流读取的匹配对（而不是在同一流/数组中相邻）。

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