A parallel implementation of hybridized merge-quicksort algorithm on MPICH

Mergesort and quicksort algorithms are two well-known sorting algorithms that have, in fact, great potential for parallel execution. This paper shows how the two are combined hand-in-hand for sorting large groups of data elements. Hierarchically, data elements are distributed to processors, sorted in smaller groups of data elements in parallel on each processor by using quicksort algorithm, and, later, merged in parallel by using mergesort algorithm. The implementation results on MPICH platform are showing potential speedups provided that the communication channel is adequate for large groups of data elements. Otherwise, longer execution time would be the problem when the data elements have to be transferred between processors. Nevertheless, the hybridized merge-quicksort algorithm is worth of consideration for parallel sorting implementation.