An enhanced multiway sorting network based on n-sorters
Feng Shi, Zhiyuan Yan, Meghanad D. Wagh · 2014
Merging-based sorting networks are an important family of sorting networks. Most merge sorting networks are based on 2-way or multi-way merging algorithms using 2-sorters as basic building blocks. An alternative is to use n-sorters, instead of 2-sorters, as the basic building blocks so as to greatly reduce the number of gates as well as the latency. Based on a modified Leighton's columnsort algorithm, an n-way merging algorithm, referred to as SS-Mk, that uses n-sorters as basic building blocks was proposed. In this work, we first propose a new multiway merging algorithm with n-sorters as basic building blocks that merges n sorted lists of m values each in 1 + ⌈m/2⌉ stages (n ≤ m). Based on our merging algorithm, we also propose a multiway sorting algorithm. We also show an application of our sorting algorithm with sorters implemented in threshold logic. Though both our algorithm and the SS-Mk require the same asymptotic number of gates, O(N log2N), to sort N inputs, our algorithm requires fewer gates than the SS-Mk for wide ranges of N.