Heuristic framework for parallel sorting computations

Abstract

Parallel sorting techniques have become of practical interest with the advent of new multiprocessor architectures. The decreasing cost of these processors will probably in the future, make the solutions that are derived thereof to be more appealing. Efficient algorithms for sorting scheme that are encountered in a number of operations are considered for multi-user machines. A heuristic framework for exploiting parallelism inherent in some of these schemes are worthy of investigation and valid suggestions are given for adequate implementation by associating processors in a multiprocessor platform. This exercise involves a closer investigation of the associated savings in employing simultaneous sorting techniques for, say N2 processors. A deterministic o(log₂N) time algorithm using Nlog₂N processors will substantially reduce the run time for a sorting scheme and is considered to be asymptotically optimal.

Journal of the Nigerian Association of Mathematical Physics Vol. 10 2006: pp. 413-422