Bitonic sorters of minimal depth (Q533870): Difference between revisions

The well-written paper deals with the problem of constructing (acyclic) comparator networks of minimal depth for sorting bitonic input sequences. A bitonic sequence (of \(n\) keys) is defined by the authors as a rotation of a concatenation of two sequences -- an ascending sequence followed by a descending one. For sorting bitonic sequences of \(n\) keys the authors construct a network of comparators (i.e. combinational devices sorting two elements) with depth equal to \(\lceil\log(n)\rceil+1\). This is an improvement of the previous known result, where such a network was constructed only for sequences with the number of keys equal to a power of two. The network is presented by the authors in the clever graphical representation. In the proof the authors use their own concept of weakly symmetric networks, where the input-to-output transformation is symmetric. The only (minor) defect is that the authors refer to the technical report (probably unpublished paper) where they proved the key lower bound on the depth of bitonic sorters.