Abstract
This paper introduces a new sorting network, called the balanced sorting Network, that sorts n items in 0 (f Ig 11]2) time using (021)(Ig n)~ 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 Ig 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 directions of the comparitors are all identical and fixed.