Large (g,d) Sorting Networks.

With only a few exceptions the minimum-comparator N-sorter networks employ the generalized divide-sort-merge strategy. That is, the N inputs are divided among g or 2 smaller sorting networks -- of size N1,N2,...,Ng, where N summation from k 1 to g of N sub k -- that comprise the initial portion of the N-sorter network. The remainder of the N-sorter is a comparator network that merges the outputs of the N1-,N2-,..., and Ng-sorter networks into a single sorted sequence. The most economical merge networks yet designed, known as the g,d merge networks, consist of d smaller merge networks -- where d is a common divisor of N1,N2,...Ng -- followed by a special comparator network labeled a g,d f-network. The paper describes special constructions for 2 sup r, 2 sup r f-networks. Author