Bollobás, Béla; Hell, Pavol Sorting and graphs. (English) Zbl 0579.68041 Graphs and order. The role of graphs in the theory of ordered sets and its applications, Proc. NATO Adv. Study Inst., Banff/Can. 1984, NATO ASI Ser., Ser. C 147, 169-184 (1985). [For the entire collection see Zbl 0549.00002.] This interesting paper discusses the number of binary comparisons needed (in a comparison tree model) to sort n elements in k time units. The authors survey in depth most of the many recent results in this area, especially those which deal with the case of fixed k. The results for this case have a highly graph theoretic flavour and the methods used are probabilistic arguments and extremal-graph-theory techniques. We mention one typical result: for every fixed k, the number of comparisons needed to sort n elements in k time units is between \(c_ 1(k)n^{1+1/k}\) and \(c_ 2(k)n^{1+1/k}\log n\). Reviewer: N.Alon Cited in 1 ReviewCited in 2 Documents MSC: 68P10 Searching and sorting 05C35 Extremal problems in graph theory 68R10 Graph theory (including graph drawing) in computer science 05A15 Exact enumeration problems, generating functions Keywords:sorting in rounds; parallel sorting; number of binary comparisons; comparison tree Citations:Zbl 0549.00002 PDFBibTeX XML