New Sorting Algorithm Wave Sort (W-Sort)
Fuente:
arXiv
Gespeichert in:
| 1. Verfasser: | |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2025
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866909980566749184 |
|---|---|
| author | Wei, Jia Xu |
| author_facet | Wei, Jia Xu |
| contents | Modern comparison sorts like quicksort suffer from performance inconsistencies due to suboptimal pivot selection, leading to $(O(N^2))$ 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 best comparison complexity of $(N-1)$, average comparison complexity close to $(\log_2(N)!)$, and worst-case comparison complexity bounded by $(O(N(\log(N))^2))$ with a small constant factor, which could be reduced to $(O(N\log(N)))$ with hybrid sorting. The algorithm can be easily expanded to be hybridized with other sorting algorithms. Experimental results demonstrate that Wave Sort requires significantly fewer comparisons than quicksort on average (approximately 24% less) and performs close to the theoretical minimum $(\log_2(N)!)$. Wave Sort offers a compelling alternative for applications demanding consistent, predictable, and in-place sorting performance. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2505_13552 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | New Sorting Algorithm Wave Sort (W-Sort) Wei, Jia Xu Data Structures and Algorithms F.2.2 Modern comparison sorts like quicksort suffer from performance inconsistencies due to suboptimal pivot selection, leading to $(O(N^2))$ 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 best comparison complexity of $(N-1)$, average comparison complexity close to $(\log_2(N)!)$, and worst-case comparison complexity bounded by $(O(N(\log(N))^2))$ with a small constant factor, which could be reduced to $(O(N\log(N)))$ with hybrid sorting. The algorithm can be easily expanded to be hybridized with other sorting algorithms. Experimental results demonstrate that Wave Sort requires significantly fewer comparisons than quicksort on average (approximately 24% less) and performs close to the theoretical minimum $(\log_2(N)!)$. Wave Sort offers a compelling alternative for applications demanding consistent, predictable, and in-place sorting performance. |
| title | New Sorting Algorithm Wave Sort (W-Sort) |
| topic | Data Structures and Algorithms F.2.2 |
| url | https://arxiv.org/abs/2505.13552 |