The left figure below shows a sorting network of size 2. The network has a "comparator module" that has two inputs, represented as lines coming into the module from left, and two outputs, represented as lines going out to right. Note that the connecting points of input/ouptut are indicated by the black dots . The upper output is the smaller of the two inputs and the lower output is the larger. When the 2 values are the same, the value is output from both lines.
We consider a problem of constructing a sorting network of size . A sorting network of size has lines and multiple comparator modules. The numbers are given at the left end and the network sorts them in the increasing order from top to bottom and outputs them from the right end.
Comparisons of two modules of which one's output is another's input cannot be executed simultaneously in an execution step. For example, in the right figure above, the comparisons of modules 1 and 2 can be executed simultaneously in a step, but another step is required for the comparison by module 3, because the outputs of modules 1 and 2 are the inputs of module 3.
(1) Explain that the sorting network of size 3 as in the following figure outputs any 3 numbers in the increasing order.
(2) Show how to construct a sorting network of size inductively from a sorting network of size , using in total comparator modules. Describe the exact number of comparator modules as a function of .
(3) As regards your answer of (2), if we allow simultaneous operations of comparator modules in a step, how many steps are required to sort inputs?
(4) Consider the case of executing multiple comparisons simultaneously. It is known that the sorting network of size 4 can be executed in 3 steps. Construct such a sorting network of size 4 and explain the correctness of your answer.
