CS575 homework V: Pipelined Merge Sort
                    ======================================

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 


Questions:
==========

Assume that input size 'n' is a power of two, that sorters can only read 
or write exactly one number in a time step and that reading or writing one 
number takes one time step, while internal computation such as comparing two 
numbers or storing a number takes zero time steps. 

1.  How many sorters are needed to sort n numbers.

2.  How many time steps does it take to sort n numbers.

3.  Is this algorithm cost optimal?

Provide detailed explanations and/or derivations for each sub-part of the 
problem.


Except as otherwise noted, the content of this presentation is 
licensed under the Creative Commons Attribution 2.5 license.