Here is an example of a particular run of block sort using batcher's
merge. Assume that N=8 and M=2.

We begin with an array of eight numbers which I've chosen as input
(Column A -- see below).

The first thing that happens is that we break our input into blocks of
size 2, and thus there are four blocks.  We sort each of these blocks
of size two, resulting in Column B.


Now we begin to use a batcher network with the merging comparators.
Since we have 4 blocks, we use a network of 4 items.  A picture of 
such a sorting network is given in Figure 11.4 of the text, and based
on the second task in the programming assignment, we also see that the
sequence of comparator calls is 0-1 2-3 0-2 1-3 1-2. So lets walk
through this.


First step is to do the comparator on block 0 and block 1.  Block 0
currently is (4,6) and block 1 is (2,7), and so the output for this is
shown in Column C.


After the 2-3 comparator, we get Column D.
After the 0-2 comparator, we get Column E.
After the 1-3 comparator, we get Column F.
After the 1-2 comparator, we get Column G, and we are done!!!

(Why does it work?  good question!)


Column   A    B   C   D   E   F   G 
        ---  --- --- --- --- --- ---
         6    4   2   2   0   0   0
         4    6   4   4   1   1   1
         7    2   6   6   6   3   2
         2    7   7   7   7   5   3
         3    3   3   0   2   2   4
         5    5   5   1   4   4   5
         0    0   0   3   3   6   6
         1    1   1   5   5   7   7