AbstractThis 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.
RightsThis Item is protected by copyright and/or related rights.You are free to use this Item in any way that is permitted by the copyright and related rights legislation that applies to your use.For other uses you need to obtain permission from the rights-holder(s).