2025/05/19 by Wei, Jia Xu
#Data Structures and Algorithms (cs.DS) #F.2.2 #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.2505.13552
Modern comparison sorts like quicksort suffer from performance inconsistencies due to suboptimal pivot selection, leading to O(N2) worst-case complexity, while in-place merge sort variants face challenges with data movement overhead. We introduce Wave Sort, a novel in-place sorting algorithm that addresses these limitations through a dynamic pivot selection strategy. Wave Sort iteratively expands a sorted region and selects pivots from this growing sorted portion to partition adjacent unsorted data. This approach ensures robust pivot selection irrespective of dataset size, guarantees a logarithmic recursion stack depth, and enables efficient in-place sorting. Our analysis shows a worst-case comparison complexity bounded by O(N(log N)2) with a small constant factor. Experimental results demonstrate that Wave Sort requires significantly fewer comparisons than quicksort on average (approximately 24% less) and performs close to the theoretical minimum, while also incorporating adaptive techniques for efficient handling of presorted sequences. Wave Sort offers a compelling alternative for applications demanding consistent, predictable, and in-place sorting performance.