A Parallel Implementation of Dual-Pivot Quick Sort for Computers with Small Number of Processors - Mohammad F. J. Klaib; Mutaz Rasmi Abu Sara; Masud Hasan (School of Computing, Telkom University, 2020)
Sorting algorithms are heavily used. Quicksort is one of the fastest comparison-based sorting algorithms. These days almost all computing devices have multiple processors. There is a strong need of finding efficient parallel versions of the most common algorithms that are widely used. The basic version of quick sort is sequential and uses only one pivot. Recently, Yaroslavsky has proposed a modified version of the quick sort that uses two pivots and runs much faster than the single-pivot quick sort. Since then Java has incorporated this dual-pivot quick sort into its standard library for sorting. Although there are many parallel versions of the original single-pivot quick sort, there is a very few for the dual-pivot. Those few parallel versions of the dual-pivot quick sorts are compared with standard sort functions, rather than the dual-pivot quick sort itself. In this paper, we provide a parallel version of the dual-pivot quick sort algorithm of Yaroslavsky and implement it in Java. For comparison, we run both in small number of parallel processors. The experimental results show that our algorithm runs significantly faster than the Yaroslavsky’s algorithm. Moreover, our algorithm performs gradually better as the number of processors and the input size increase.