A new parallel sorting algorithm based on odd-even mergesort

Abstract

This paper describes a new parallel sorting algorithm, derived from the odd-even mergesort algorithm, named "partition and concurrent merging" (PCM). The proposed algorithm is based on a divide-and-conquer strategy. First, the data sequence to be sorted is decomposed in several pieces that are sorted in parallel using Quicksort. After that, all pieces are merged using a recursive procedure to obtain the final sorted sequence. In each iteration of this procedure pairs of sequence pieces are selected and sorted concurrently. The paper analyzes the computational complexity of the new algorithm and compares it with that of other well-known parallel sorting algorithms. We implemented the PCM algorithm on a SGI Origin2000 multiprocessor using OpenMP, sorting different benchmark sets of data sequences. Experimental results are compared with those of the Quicksort sequential algorithm and parallel implementations of other sorting algorithms, obtaining that our proposal outperforms the other solutions.