2014/07/23 by Marcello La Rocca, La Rocca, Marcello, Domenico Cantone +1
Computer Science · #68W01 #68W40 #C.2.2 #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Fuzzy Logic and Control Systems
paper · pdf · doi:10.48550/arxiv.1407.6183
openalex publication_date 2014/07/23 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We present a new adaptive sorting algorithm which is optimal for most disorder metrics and, more important, has a simple and quick implementation. On input X, our algorithm has a theoretical Ω(|X|) lower bound and a O(|X|log|X|) upper bound, exhibiting amazing adaptive properties which makes it run closer to its lower bound as disorder (computed on different metrics) diminishes. From a practical point of view, NeatSort has proven itself competitive with (and often better than) qsort and any Random Quicksort implementation, even on random arrays.