Title :
K-way bitonic sort
Author :
Nakatani, Toshio ; Huang, Shing-Tsaan ; Arden, Bruce W. ; Tripathi, Satish K.
Author_Institution :
Dept. of Comput. Sci., Princeton Univ., NJ, USA
Abstract :
The k-way bitonic sort algorithm, a generalization of K.E. Batcher´s bitonic sort algorithm (1968), is presented. This variation of the algorithm is based on a k-way decomposition instead of a two-way decomposition. It is proven that Batcher´s bitonic sequence decomposition theorem still holds with this multiway decomposition. This leads to applications of sorting networks with bitonic sorters of arbitrary or mixed sizes.<>
Keywords :
sorting; k-way bitonic sort algorithm; k-way decomposition; Sorting;
Journal_Title :
Computers, IEEE Transactions on
