Keywords
Parallel sorting
How to Cite
Abstract
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.
References
Knuth, D. E. (1997). The art of computer programming, volume 3: Sorting and searching (2nd ed.). Addison–Wesley.
Katajainen, J., & Träff, J. L. (1997). Algorithms and complexity. In Proceedings of the 3rd Italian Conference on Algorithms and Complexity.
Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2009). Introduction to algorithms (3rd. ed.). The MIT Press.
Rolfe, T. J. (2010). A specimen of parallel programming: Parallel merge sort implementation. ACM Inroads, 1(4), 72–79. http://doi.org/10.1145/1869746.1869767
Radenski, A. (2011). Shared memory, message passing, and hybrid merge sorts for standalone and clustered SMPs. In Proceedings of the 2011 International Conference on Parallel and Distributed Processing Techniques and Applications (PDPTA’11) (pp. 367–373).
Duvanenko, V. (2011). Parallel merge sort. https://duvanenko.tech.blog/2018/01/13/parallel-merge-sort/
Axtmann, M., Bingmann, T., Sanders, P., & Schulz, C. (2015). Practical massively parallel sorting. In Proceedings of the 27th ACM symposium on Parallelism in Algorithms and Architectures (pp. 13–23). https://doi.org/10.1145/2755573.2755595
Nesmachnow, S., & Iturriaga, S. (2019). Cluster-UY: Collaborative scientific high performance computing in Uruguay. In M. Torres & J. Klapp (Eds.), Supercomputing (pp. 188–202). Springer. https://doi.org/10.1007/978-3-030-38043- 4_16
This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.
Copyright (c) 2025 José Eduardo Solsona, Sergio Nesmachnow