TwinArray Sort: An Ultrarapid Conditional Non-Comparison Integer Sorting Algorithm

Amini, A (2026) TwinArray Sort: An Ultrarapid Conditional Non-Comparison Integer Sorting Algorithm. Electronics, 15 (3). pp. 1-14. ISSN 2079-9292

Preview

Text electronics-15-00609.pdf - Published Version Available under License Creative Commons Attribution. Download (2MB) | Preview

Abstract

TwinArray Sort is a non-comparison integer sorting algorithm designed for non-negative integers with relatively dense key ranges, offering competitive runtime performance and reduced memory usage relative to other counting-based methods. The algorithm introduces a conditional distinct-array verification mechanism that adapts the reconstruction strategy based on data characteristics while maintaining worst-case time and space complexity of O(n + k). Comprehensive experimental evaluations were conducted on datasets containing up to 108 elements across multiple data distributions, including random, reverse-sorted, nearly sorted, and their unique variants. The results demonstrate consistent performance improvements compared with established algorithms such as Counting Sort, Pigeonhole Sort, MSD Radix Sort, Spreadsort, Flash Sort, Bucket Sort, and Quicksort. TwinArray Sort achieved execution times up to 2.7 times faster and reduced memory usage by up to 50%, with particularly strong performance observed for unique and reverse-sorted datasets. The algorithm exhibits good scalability for large datasets and key ranges, with performance degradation occurring primarily in extreme cases where the key range significantly exceeds the input size due to auxiliary array requirements. These findings indicate that TwinArray Sort is a competitive solution for in-memory sorting in high-performance and distributed computing environments. Future work will focus on optimizing performance for wide key ranges and developing parallel implementations for multi-core and GPU architectures.

Item Type:	Article
Uncontrolled Keywords:	non-comparison integer sorting; linear-time sorting; dense key ranges; duplicate-aware algorithms; memory–time trade-offs; 0906 Electrical and Electronic Engineering; 4009 Electronics, sensors and digital hardware
Subjects:	Q Science > QA Mathematics > QA75 Electronic computers. Computer science T Technology > T Technology (General) > T58.5 Information Technology
Divisions:	Computer Science and Mathematics
Publisher:	MDPI AG
Date of acceptance:	27 January 2026
Date of first compliant Open Access:	2 February 2026
Date Deposited:	02 Feb 2026 14:38
Last Modified:	02 Feb 2026 14:38
DOI or ID number:	10.3390/electronics15030609
URI:	https://researchonline.ljmu.ac.uk/id/eprint/28025

View Item