A Parallel Implementation of Dual-Pivot Quick Sort for Computers with Small Number of Processors
T. H. Cormen, C. E. Leiserson, and R. L. Rivest, Introduction to Algorithms, 3rd ed. Cambridge, Massachusetts, USA, MIT Press, 2009.
D. E. Knuth, The Art of Computer Programming volume 3: Sorting and Searching, 2nd ed. Addison-Wesley. 1998.
P. Sanders, K. Mehlhorn, M. Dietzfelbinger, and R. Dementiev, Sequential and Parallel Algorithms and Data Structures - The Basic Toolbox, Springer, 2019.
C. A. R. Hoare. (1962). Quicksort. Computer Journal. volume(5), pp. 10–16.
B. A. Cipra. (2000, May). The best of the 20th century: Editors name top 10 algorithms. SIAM News. volume(33), pp. 1-2.
R. Sedgewick. (1977). The analysis of quicksort programs, Acta Informatica. volume(7), pp. 327–355.
S. Wild and M. E. Nebel. (2012). Average case analysis of Java 7’s dual pivot quicksort. ESA, LNCS, Springer, Berlin. volume(7501), pp. 825–836.
J. Dongarra and F. Sullivan. (2000, January/February). Introduction: the top 10 algorithms, computing in science & engineering. IEEE. volume 2, pp. 22-23.
S. Taotiamton and S. Kittitornkun. (2017, November). A parallel dual-pivot quicksort algorithm with lomuto partition. 21st International Computer Science and Engineering Conference (ICSEC), Bangkok, Thailand, IEEE, pp. 15-18.
S. Taotiamton and S. Kittitornkun. (2017, June). Parallel hybrid dual pivot sorting algorithm. 14th International Conference on Electrical Engineering/Electronics, Computer, Telecommunications and Information Technology (ECTI-CON), Phuket, Thailand, IEEE, pp. 27-30.
M. E. Nebel, S. Wild and C. Martínez. (2016). Analysis of pivot sampling in dual-pivot quicksort: a holistic analysis of Yaroslavskiy’s partitioning scheme. Algorithmica, Springer. volume (75), pp. 632-683.
S. Wild, M. E Nebel, and R. Neininger. (2015, January). Average case and distributional analysis of dual-pivot quicksort. ACM Transactions on Algorithms. volume (11), pp. 22.
S. Wild, M. E. Nebel and H. Mahmoud. (2016). Analysis of quickselect under Yaroslavskiy’s dual-pivoting algorithm. Algorithmica. volume (74), pp. 485–506.
S. Kushagra, A. López-Ortiz, J. I. Munro, and A. Qiao. (2014, January). Multi-pivot quicksort: theory and experiments. Proceedings of the Meeting on Algorithm Engineering & Expermiments (ALENEX), SIAM, pp. 47–60.
V. Yaroslavsky. (2009, September). Dual-Pivot Quicksort algorithm. Available: https://codeblab.com/wp-content/uploads/2009/09/DualPivotQuicksort.pdf.
S. S. M. Al-Dabbagh and N. H. Barnouti. (2016, June). Parallel quicksort algorithm using OpenMP. International Journal of Computer Science and Mobile Computing. volume (5), pp.372–382.
P. Sanders and T. Hansch. (1997). Efficient massively parallel quicksort. International Symposium on Solving Irregularly Structured Problems in Parallel IRREGULAR 1997, Springer LNCS. volume (1253), pp. 13-24.
P. Tsigas and Y. Zhang. (2003, February). 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, Genova, Italy, IEEE, volume(5-7), pp. 372-381.
D. Cederman and P. Tsigas, (2010, January). GPU-Quicksort: a practical quicksort algorithm for graphics processors. Journal of Experimental Algorithmics, pp. 4.
D. Pasetto and A. Akhriev, (2011, October). A comparative study of parallel sort algorithms. proceedings of the ACM International Conference Companion on Object Oriented Programming Systems Languages and Applications, Portland, Oregon, USA, pp. 203-204.
B. A. Mahafzah. (2013). Performance assessment of multithreaded quicksort algorithm on simultaneous multithreaded architecture. Journal of Supercomputing, Springer. volume (66), pp. 339–363.
A. Rattanatranurak, (2018, June). Dual parallel partition sorting algorithm. Proceedings of 2018 the 8th International Workshop on Computer Science and Engineering (WCSE 2018), Bangkok, pp. 685 -690.
GeeksforGeeks. (2020). Serial Sort v/s Parallel Sort in Java. Available: https://www.geeksforgeeks.org/serial-sort-vs-parallel-sort-java/
Copyright (c) 2020 Mohammad F. J. Klaib, Mutaz Rasmi Abu Sara, Masud Hasan
This work is licensed under a Creative Commons Attribution 4.0 International License.
- Manuscript submitted to IndoJC has to be an original work of the author(s), contains no element of plagiarism, and has never been published or is not being considered for publication in other journals.
- Copyright on any article is retained by the author(s). Regarding copyright transfers please see below.
- Authors grant IndoJC a license to publish the article and identify itself as the original publisher.
- Authors grant IndoJC commercial rights to produce hardcopy volumes of the journal for sale to libraries and individuals.
- Authors grant any third party the right to use the article freely as long as its original authors and citation details are identified.
- The article and any associated published material is distributed under the Creative Commons Attribution 4.0License