A Generalization of the Divide-Sort-Merge Strategy for Sorting Networks
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 (1/2 N) and (1/2 N)* - - 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 (1/2 N) - 1 comparators. The paper considers a generalization of the divide- sort-merge strategy in which the N inputs are divided into g > or = 2 disjoint groups that are sorted independently and then merged together.
Document Details
- Document Type
- Technical Report
- Publication Date
- Aug 01, 1971
- Accession Number
- AD0737270
Entities
People
- David C. Van Voorhis
Organizations
- Stanford University