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

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.