ech@spuxll.UUCP (Ned Horvath) (06/26/85)
No such thing, unless you know one HELL of a lot about your data (like only the first O(1) items are disordered -:) A result analogous to the decision-tree lower-bound of nlogn is the one for sorting nets (see Knuth v.3, section 5.3.4). Best known nets are ~n/2 comparators wide and O((logn)^2) deep; the principle is effectively logn cascades of an O(logn) deep merging network. For purposes of this discussion a comparator has two inputs and two outputs; the outputs are the reverse of the inputs if they are disordered. An alternative model uses just n/2 comparators and feeds the output of each stage through permutation logic and back into the comparators, but still O(logn squared) "cycles" are needed. The simplest such net does a repeated perfect shuffle of outputs to inputs. It is noteworthy that O(logn) has been shown to be optimal for parallel merging; to my knowledge it is still open whether O(logn squared) is a lower bound for sorting. =Ned=