The balanced sorting network

Publisher Website
Google Scholar
Abstract
This paper introduces a new sorting network, called the balanced sorting network, that sorts n items in O([lgn]2) time using (n/2)(lgn)2 comparators. Although these bounds are comparable to many existing sorting networks, the balanced sorting network possess some distinct advantages. In particular, its structure is highly regular consisting of a sequence of identicalbalanced 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.

This publication has 0 references indexed in Scilit: