BALANCED SORTING NETWORK.

This paper introduces a new sorting network, called the balanced sorting network, that sorts n items in OMICRON ( left bracket lg n right bracket **2) time using (n/2)(lg n)**2 comparators. Although these bounds are comparable to many existing sorting networks, the balanced sorting network possesses some distinct advantages. In particular, its structure is highly regular consisting of a sequence of identical balanced merging networks. We prove that lg n identical merging networks are both necessary and sufficient to sort n items. We also present an explicit implementation of our network on the shuffle exchange interconnection model in which the direction of the comparitors are all identical and fixed.