Based On The Efficient Merge Sorting Algorithm

Sorting has a broad range of application, such as in compilers, operating systems, database systems, routing and permutation networks. Statistics shows that 25-50% of all the work performed by computers consists of sorting data. Therefore, for both practical and theoretical reasons, sorting is probably one of the most widely studied problems in computer science.The current situation of research and development in parallel sorting is reviewed first. We find that merge sorting is one of the important methods in sorting field. Most merge sorting algorithms adopt 2-sorters as their basic units in their implementations. A 2-sorters means the comparison and exchange of 2 items. Is it possible, as the generalization of 2-sorters, to construct sorting algorithms based solely on k-sorters as the basic unit instead of 2-sorters? A k-sorters sorts k items in one step, where k is of any integer greater than or equal to 2. Another question is whether sorting based solely on k-sorters has any benefits as compared with sorting based on 2-sorters. In this paper, we present the following results.First, We present a multiway merging algorithm, called ISS-Mk, which is based on k-sorters and k can be any integer. ISS-Mk does not rely on 2-sorters anymore. We also give a parallel sorting algorithm— ISS-Sk based on ISS-Mk.Second, in ISS-Mk, we combine sloping-and-shaking with block...