Institution: Stanford University, Department of Computer Science

Title: A generalization of the divide-sort-merge strategy for sorting networks

Author: Van Voorhis, David C.

Date: August 1971

Abstract: With a few notable exceptions the best sorting networks known have employed a "divide-sort-merge" strategy. That is, the N inputs are divided into 2 groups - - normally of size $\lceil \frac{1}{2} N\rceil$ and $\lfloor \frac{1}{2} N\rfloor$ [Here $\lceil x\rceil$ denotes the smallest integer greater than or equal to x, whereas $\lfloor x\rfloor$ denotes the largest integer less than or equal to x] - - that are sorted independently and then "merged" together to form a single sorted sequence. An N-sorter network that uses this strategy consists of 2 smaller sorting networks followed by a merge network. The best merge networks known are also constructed recursively, using 2 smaller merge networks followed by a simple arrangement of $\lceil \frac{1}{2} N\rceil$ - 1 comparators. We consider a generalization of the divide-sort-merge strategy in which the N inputs are divided into g $\geq$ 2 disjoint groups that are sorted independently and then merged together. The merge network that combines these g sorted groups uses d $\geq$ 2 smaller merge networks as an initial subnetwork. The two parameters g and d together define what we call a "[g,d]" strategy. A [g,d] N-sorter network consists of g smaller sorting networks followed by a [g,d] merge network. The initial portion of the [g,d] merge network consists of d smaller merge networks; the final portion, which we call the "f-network," includes whatever additional comparators are required to complete the merge. When g = d = 2, the f-network is a simple arrangement of $\lceil \frac{1}{2} N\rceil$ - 1 comparators; however, for larger g,d the structure of the [g,d] f-network becomes increasingly complicated. In this paper we describe how to construct [g,d] f-networks for arbitrary g,d. For N > 8 the resulting [g,d] N-sorter networks are more economical than any previous networks that use the divide-sort-merge strategy; for N > 34 the resulting networks are more economical than previous networks of any construction. The [4,4] N-sorter network described in this paper requires $\frac{1}{4} N{(log_2 N)}^2\ - \frac{1}{3} N(log_2 N) + O(N)$ comparators, which represents an asymptotic improvement of $\frac{1}{12} N(log_2 N)$ comparators over the best previous N-sorter. We indicate that special constructions (not described in this paper) have been found for [$2^r , 2^r$] f-networks, which lead to an N-sorter network that requires only .25 $N{(log_2 N)}^2\ - .372 N(log_2 N) + O(N)$ comparators.

http://i.stanford.edu/pub/cstr/reports/cs/tr/71/237/CS-TR-71-237.pdf