Empirical evaluation of parallel implementations of MergeSort

Sorting algorithms are a fundamental piece in the development of computer systems. MergeSort is a well-known sorting algorithm, much appreciated due to its efficiency, relative simplicity, and other features. This article presents an empirical evaluation of parallel versions of MergeSort, applying shared and distributed memory, on a high-performance computing infrastructure. The main result indicates that parallelization of recursive invocations combined with a parallel merge operation offers better speedup than just parallelization of recursive invocations. Moreover, better speedup was achieved in a shared memory environment.