Parallel sorting machines

Publisher Website
Google Scholar
Abstract
A unified approach for analyzing and classifying parallel sorting machines is discussed. The approach accounts for a number of important factors that have significant impacts on the measure of the size and complexities of parallel sorters. These factors include the sorter architectures, sequential/parallel input, single/multiple passes, and the base of the comparitors. An efficiency measure is also introduced to describe the optimality and other general characteristics of the sorters. Finally, a new sorter with the time complexity of O(c*logbN), where b is an arbitrary base, is proposed. Its efficiency is independent of the number of processors, the size of the list, and the maximum value in the list.

This publication has 0 references indexed in Scilit: