A Hypercubic Sorting Network with Nearly Logarithmic Depth

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

Authors

• C. Greg Plaxton

Keywords

No keywords are indexed for this paper.