An Optimal Parallel Sorting Algorithm for Multisets

Sorting is a very interesting problem that has the important theoretical significance and widely applied value Sorting for multisets is to sort n numbers （records） that contain only k distinct key values, where 0＜k＜n In this paper, based on the idea of "median of medians" and principle of "filtering", a deterministic and stable parallel sorting algorithm for multisets is presented When the algorithm is executed recursively, some data with the same key values are filtered logically and the processors are assigned to the subtasks adaptively and dynamically in order to balance their computing loads For the shared memory parallel systems with p=n 1-ε processors, where 0＜ ε ＜1, the algorithm requires O（（n/p+p ε） log k ） time and gets optimal O（n log k ） cost on CREW PRAM; its time complexity is O（（n/p+p ε +log p ）log k ）, and its corresponding cost is also optimal when plogp≤n on EREW PRAM The main contribution of the paper is to present a new parallel sorting approach by applying selection technique