SLOPING-AND-SHAKING - MULTIWAY MERGING AND SORTING

Most traditional merging and merging-based sorting algorithms are base d on 2 sorters or 2 comparators. A new merging technique is developed, namely sloping-and-shaking multiway merging, and a corresponding mult iway sorting method based only on k-sorters is proposed. The sloping-a nd-shaking merging algorithm merges k sorted lists into one, where k c an be any prime number. The merging process is not a series of recursi ve applications of 2-way merging. It sorts the keys on the m x k plane in vertical and horizontal directions, then along sloping lines with various slope rates step by step. Only k-sorters are needed in the mer ging or sorting process. The time needed to merge k sorted lists, with m of each, is (k + inverted right perpendicular log(2)(m/k) inverted left perpendicular)t(k), and the time for sorting N keys is (1 + (p - 1)k + 1/2(p - 1)(p - 2) inverted right perpendicular log(2)k inverted left perpendicular)t(k), where p = log(k)N, and t(k) is the time to so rt k keys. The proposed algorithms can be implemented either by hardwa red sorting networks, or on general purpose parallel and vector machin es. The traditional odd-even merging can be viewed as a special case o f the multiway merging proposed (when k is 2). While theoretically the proposed algorithms provide a new understanding of parallel merging a nd sorting processes, they may be used in practice to construct sortin g circuits faster than 2-sorter based sorting methods.