作者: C. Greg Plaxton
关键词:
摘要: A natural class of “hypercubic” sorting networks is defined. The regular structure these allows for elegant and efficient implementations on any the so-called hypercubic (e.g., hypercube, shuffle-exchange, butterfly, cube-connected cycles). This contains Batcher's O(lg2n)-depth bitonic sort, but not O(lg n)-depth network Ajtai, Komlo´s, Szemere´di. In fact, no o(lg2n)-depth compare-interchange sort was previously known networks. this paper, we prove existence a family 2O((lg lg n)1/2) n-depth Note that depth o(lg1+en) constant e > 0.