# Assignment 15 - Parallel Sorting

1. Getting Started

2. Outline

Comparators are small devices which have two inputs and two outputs. The first output is the minimum and the second the maximum of the two numbers at the input. So a comparator sorts two numbers two a list. One can arrange comparators such that they form a sorting network. An example of such an architecture are the odd-even sorting networks on pages 264-265 in Chapter 10 of Harel's book. The goal is to have several comparators in parallel in order to sort with as few levels as possible. Each level has 10 inputs and 10 outputs. Some neighbouring inputs might be sent into a comparator with the results then sent to some output fields and other inputs are without being compared directly moved to some output. There are at most 5 comparators per level and every input is dealt with exactly once. More details are given in next section.

3. The syntax for describing a level

Each level is described by a certain code. This code consists of commands about what to do in the level. The command consists of a sequence of move commands like m9- which moves the current input to the place 9 for the next level and comparators like c34 which takes two current inputs and assign their minimum to the place 3 and their maximum to the place 4. The combined command consists of several 3-digit-codes and has therefore a length which is a multiple of 3. Here is an example:

```       Complete code:  "m9-c12c34c87m6-c50", inputs are determined
by positions of subcodes in code, outputs are explicitly stated.

"m9-": input at "0" is Moved to "9";
"c12": inputs at "1" and "2" are sent into a Comparator
and the results are sent to "1" and "2";
"c34": inputs at "3" and "4" are sent into a Comparator
and the results are sent to "3" and "4";
"c87": inputs at "5" and "6" are sent into a Comparator
and the results are sent to "8" and "7";
"m6-": input at "7" is Moved to "6";
"c50": inputs at "8" and "9" are sent into a Comparator
and the results are sent to "5" and "0".

Sample Execution of level:
Position   "0"  "1"  "2"  "3"  "4"  "5"  "6"  "7"  "8"  "9"
Before      10   90   80   70   77   66   55   88   39   28
Command     m9-  c12       c34       c87       m6-  c50
After       28   80   90   70   77   39   88   66   55   10 ```

The incoming data of a comparator or move command is just determined by the position in the level description, the outgoing positions are explicitly declared by digits. The coded operation should address all positions and cover all inputs of the next level. Therefore every digit has to appear exactly once in the code. For easier interpretation, the move instructions also have three digits with a - filling the third useless character. m stands for moving an input, c stands for comparing two inputs in a comparator. Note that even if the input moves to the same position in the output, a moving command must be placed. A command like c87 places the larger output first and the smaller one second; this is legal but does not give any advantage, therefore it is recommended not to do that. The goal is to have the resulting list be ordered in an ascending way.