This study explores the application of parallel algorithms to enhance large-scale sorting, focusing on the QuickSort method. Implemented in both sequential and parallel forms, the paper provides a detailed comparison of their performance. This study investigates the efficacy of both techniques through the lens of array generation and pivot selection to manage datasets of varying sizes. This study meticulously documents the performance metrics, recording 16,499.2 milliseconds for the serial implementation and 16,339 milliseconds for the parallel implementation when sorting an array by using C++ chrono library. These results suggest that while the performance gains of the parallel approach over its serial counterpart are not immediately pronounced for smaller datasets, the benefits are expected to be more substantial as the dataset size increases.
References
[1]
Baqer, Z.T. (2018) Parallel Computing for Sorting Algorithms. https://www.researchgate.net/publication/328465897_Parallel_Computing_for_Sorting_Algorithms
Heidelberger, P., Norton, A. and Robinson, J.T. (1990) Parallel Quicksort Using Fetch-and-Add. IEEE Transactions on Computers, 39, 133-138. https://doi.org/10.1109/12.46289
[4]
Sintorn, E. and Assarsson, U. (2008) Fast Parallel GPU-Sorting Using a Hybrid Algorithm. Journal of Parallel and Distributed Computing, 68, 1381-1388. https://doi.org/10.1016/j.jpdc.2008.05.012
[5]
Tsigas, P. and Zhang, Y. (2003) A Simple, Fast Parallel Implementation of Quicksort and Its Performance Evaluation on SUN Enterprise 10000. Eleventh Euromicro Conference on Parallel, Distributed and Network-Based Processing, 2003. Proceedings, Genova, 5-7 February 2003, 372-381. https://doi.org/10.1109/EMPDP.2003.1183613
[6]
Reinders, J. (2007) Intel Threading Building Blocks. O’Reilly Media, Inc., Sebastopol, CA.
[7]
Singh, T., Srivastava, D.K. and Aggarwal, A. (2017) A Novel Approach for CPU Utilization on a Multicore Paradigm Using Parallel Quicksort. 2017 3rd International Conference on Computational Intelligence & Communication Technology (CICT), Ghaziabad, 9-10 February 2017, 1-6. https://doi.org/10.1109/CIACT.2017.7977382
[8]
Marszałek, Z., Woźniak, M. and Połap, D. (2018) Fully Flexible Parallel Merge Sort for Multi-core Architectures. Complexity, 2018, Article ID: 8679579. https://doi.org/10.1155/2018/8679579
[9]
ISO/IEC (2017) ISO/IEC 14882: C++ standard library. International Organization for Standardization, Geneva.
[10]
Sedgewick, R. (1978) Implementing Quicksort Programs. Communications of the ACM, 21, 847-857. https://doi.org/10.1145/359619.359631
[11]
Dagum, L. and Menon, R. (1998) OpenMP: An Industry-Standard API for Shared-Memory Programming. IEEE Computational Science & Engineering, 5, 46-55. https://doi.org/10.1109/99.660313
