A strategy for parallel sorting algorithms evaluation based on MPI technology

The message-passing architectures consist of multiple computers interconnected through an interconnection network, communicating one with other by send-receive message functions and synchronized by barrier functions. Message Passing Interface (MPI) is a C/C++ functions library usefull to implement the parallel algorithms on message-passing architectures. In this paper we propose three parallel sorting algorithms (Insertsort, Bubblesort and Quicksort), and we propose a strategy to evaluate their performances. The algorithms are designed for message-passing architectures and implemented using MPI library. We evaluate the performances of each algorithm on three types of message passing architectures: linear array, two-dimensional mesh and hypercube. We evaluate the sorting time, the interprocesses communication time and the total processing time for each topology and we analyze the efficiency of the proposed parallel sorting algorithms related to the parallel system topology.