PentaSort: A New Sorting Method
DOI:
https://doi.org/10.66395/globeis.6Keywords:
Penta Sort, Sorting algorithms, Block sorting, Median of medians, Comparison-based sorting, Algorithm analysisAbstract
PentaSort is a comparison-based sorting algorithm built on three main ideas: block fusion, dual-pivot partitioning, and sorted-block binary partitioning. The input is first divided into 5-element blocks, and each block is sorted by a fixed local procedure. Adjacent blocks are then checked, and those already in the correct order are fused; this step gives O(n) behavior for nearly sorted inputs. Two pivots are next selected deterministically from the first and third quartiles of the block medians, and the input is partitioned into three parts. The sorted-block structure is also used during partitioning to reduce the number of comparisons. The results show that PentaSort achieves O(n log n) time complexity in both the average and worst cases. These findings indicate that the proposed method offers a simple, deterministic, and adaptive sorting framework.
Downloads
References
1. Boticki, I., Barisic, A., Martin, S., & Drljevic, N. (2013). Teaching and learning computer science sorting algorithms with mobile devices: A case study. Computer Applications in Engineering Education, 21(S1), E41–E50.
2. Estivill-Castro, V., & Wood, D. (1992). A survey of adaptive sorting algorithms. ACM Computing Surveys (CSUR), 24(4), 441–476.
3. Rizvi, Q. M., Rai, H., & Jaiswal, R. (2024). Sorting algorithms in focus: A critical examination of sorting algorithm performance. In Emerging Trends in IoT and Computing Technologies (pp. 103–106). CRC Press.
4. Roșca, C.-M., & Cărbureanu, M. (2024). A comparative analysis of sorting algorithms for large-scale data: Performance metrics and language efficiency. International Conference on Emerging Trends and Technologies on Intelligent Systems.
5. Kahale, N., Leighton, T., Ma, Y., Plaxton, C. G., Suel, T., & Szemerédi, E. (1995). Lower bounds for sorting networks. Proceedings of the Twenty-Seventh Annual ACM Symposium on Theory of Computing.
6. Asharov, G., Lin, W.-K., & Shi, E. (2022). Sorting short keys in circuits of size o(n log n). SIAM Journal on Computing, 51(3), 424–466.
7. Yuan, G. L., Bakhoda, A., & Aamodt, T. M. (2009). Complexity effective memory access scheduling for many-core accelerator architectures. Proceedings of the 42nd Annual IEEE/ACM International Symposium on Microarchitecture.
8. Wibowo, F. R., & Faisal, M. (2024). Comparative analysis of sorting algorithms: TimSort Python and classical sorting methods. JISA (Jurnal Informatika dan Sains), 7(1), 11–18.
9. Yaroslavskiy, V. (2009). Dual-pivot quicksort. Research Disclosure.
10. De Gouw, S., Rot, J., de Boer, F. S., Bubel, R., & Hähnle, R. (2015). OpenJDK's java.utils.Collection.sort() is broken: The good, the bad and the worst case. International Conference on Computer Aided Verification.
11. Blum, M., Floyd, R. W., Pratt, V. R., Rivest, R. L., & Tarjan, R. E. (1973). Time bounds for selection. Journal of Computer and System Sciences, 7(4), 448–461.
12. Musser, D. R. (1997). Introspective sorting and selection algorithms. Software: Practice and Experience, 27(8), 983–993.
13. Schaffer, R., & Sedgewick, R. (1993). The analysis of heapsort. Journal of Algorithms, 15(1), 76–100.
14. Wild, S., & Nebel, M. E. (2012). Average case analysis of Java 7's dual pivot quicksort. European Symposium on Algorithms.
15. Munro, J. I., & Wild, S. (2018). Nearly-optimal mergesorts: Fast, practical sorting methods that optimally adapt to existing runs. arXiv preprint arXiv:1805.04154.
16. Buss, S., & Knop, A. (2019). Strategies for stable merge sorting. Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms.
17. Mannila, H. (2009). Measures of presortedness and optimal sorting algorithms. IEEE Transactions on Computers, 100(4), 318–325.
18. Donald, E. K. (1999). The art of computer programming. Sorting and Searching, 3(426–458), 4.
19. Alexandrescu, A. (2016). Fast deterministic selection. arXiv preprint arXiv:1606.00484.
20. Cole, R. (1988). Parallel merge sort. SIAM Journal on Computing, 17(4), 770–785.
21. Lammich, P. (2020). Efficient verified implementation of introsort and pdqsort. International Joint Conference on Automated Reasoning.
22. Kushagra, S., López-Ortiz, A., Qiao, A., & Munro, J. I. (2014). Multi-pivot quicksort: Theory and experiments. 2014 Proceedings of the Sixteenth Workshop on Algorithm Engineering and Experiments (ALENEX).
Downloads
Published
Issue
Section
License
Copyright (c) 2026 GlobeIS International Journal of Global Information Systems
This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.
