K-Way Bitonic Sort

Abstract:

The paper presents k-way bitonic sort, which is the generalization of Batcher's bitonic sort. K-way bitonic sort is based on the k-way decomposition scheme instead of two-way decomposition. We prove that Batcher's bitonic sequence decomposition theorem still holds with multi-way decomposition. This
leads to the applications of the sorting network with bitonic sorters of arbitrary or mixed sizes.