Periodic sorting using minimum delay, recursively constructed merging networks (Q1379127)

Summary: Let \(\alpha\) and \(\beta\) be a partition of \(\{1,\ldots,n\}\) into two blocks. A merging network is a network of comparators which allows as input arbitrary real numbers and has the property that, whenever the input sequence \(x_1,x_2,\ldots,x_n\) is such that the subsequence in the positions \(\alpha\) and the subsequence in the positions \(\beta\) are each sorted, the output sequence will be sorted. We study the class of ``recursively constructed'' merging networks and characterize those with delay \(\lceil\log_2 n\rceil\) (the best possible delay for all merging networks). When \(n\) is a power of 2, we show that at least \(3^{n/2-1}\) of these nets are log-periodic sorters; that is, they sort any input sequence after \(\log_2n\) passes through the net. (Two of these have appeared previously in the literature.).