nemo@rochester.UUCP (Wolfe) (06/28/85)
> 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. > > 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= Refer to the Procedings of the 15th Annual ACM Symposium on Theory of Computing (STOC). The first paper is the historic "three Hungarians" sorting network result (Ajtai, Komlo's and Szemere'di, "An O(n log n) Sorting Network," pp. 1-9). They present a network of size O(n log n) and depth O(log n) (hence O(log n) time) based on expander graphs. An earlier version appeared in Combinatorica. The constant in the big O is large due to properties of the expander graphs used (these turn out to be difficult to construct, but easy to find in the sense that a random bitartite graph is likely to be one). They note that Batcher's sort (the one on which the log squared delay networks are based) is better for all but very large input sizes. Nemo -- Internet: nemo@rochester.arpa UUCP: {decvax, allegra, seismo, cmcl2}!rochester!nemo Phone: [USA] (716) 275-5766 work, 232-4690 home USMail: 104 Tremont Circle; Rochester, NY 14608 School: Department of Computer Science; University of Rochester; Rochester, NY 14627