The latest CS2020 assignment contains this problem (slightly paraphrased): given blocks of data (with each block being of size , with the primitive operation of sorting any two blocks of data together (i.e. take two blocks, concatenate, sort, then split back into two blocks), devise an algorithm to sort all blocks of data. Inspection of the elements within each block is not allowed.
The first thing to note is that we must have , because we cannot sort a single block on its own. (A bizarre restriction.) The second thing to note is that because our sorting algorithm necessarily acts independent of the data, we may treat it as being similar to a sorting network and make use of the 0-1 principle (where every individual datum is either “0” or “1”) to simplify analysis. The third thing to note is that, without loss of generality, we may assume that the contents of the individual blocks are already sorted, and equivalently, we may also treat a block as containing an integer between 0 and , inclusive.
Why does the 0-1 principle hold? This is not trivial (the standard proof does not immediately generalise), but we can always convert a block sorting network into a normal sorting network by substituting the sort-two-blocks operation with a sorting network; therefore the 0-1 principle remains valid.
Define a block comparator as the primitive operation of sorting two blocks together. In the case where , this is obviously analogous to comparators in normal sorting networks.
A clean block is a block where all elements are identical; a mixed block is a block with both 0’s and 1’s. Any sorted block sequence has at most one mixed block.
We could directly adapt the bubble/insertion network to this problem, and this gives a block-sorting network with block comparators and depth . Correctness may be proven via induction, as for the original sorting network. To be more precise, the insertion network for elements is given by the concatenation of the insertion passes over , where each insertion pass consists of the (block) comparators . Visually, it looks like this:
(Image source: https://en.wikipedia.org/wiki/File:Six-wire-insertion-sorting-network.svg; licensed under CC-BY 3.0.)
If , the sole block comparator in the network sorts both blocks. Done. Suppose the network is correct for some ; we will proceed to show correctness for , whence by induction correctness is proven for all .
By the inductive hypothesis, after the first passes the first blocks are sorted. Consider what the th pass does. If all the blocks are clean, this reduces to insertion sort and we are done. If the first blocks are all-zero, we are done. Otherwise, let be the index of the first block among the first that is not all-zero. As the subsequence of blocks over the indices is sorted, the blocks after index are all-one. Applying the comparators shifts the last block next to block . Applying the comparator completes the sort.
The insertion network is not the only one that still sorts correctly when adapted to block-sorting. A careful case analysis (>>cases) shows that the odd-even merge sort (with the generalisation to non-power-of-two sizes) has the same property; bitonic merge sort can also be proven to be correct when applied to block-sorting.
This does bring up the question: do all sorting networks work as block-sorting networks? It’s not obvious whether we can force a contradiction from a sorting network that works when but not for some larger value of .