Towards universally optimal sorting algorithms
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_ | 1866915605340225536 |
|---|---|
| author | Sen, Sandeep |
| author_facet | Sen, Sandeep |
| contents | We formalize a new paradigm for optimality of algorithms, that generalizes worst-case optimality based only on input-size to problem-dependent parameters including implicit ones. We re-visit some existing sorting algorithms from this perspective, and also present a novel measure of sortedness that leads to an optimal algorithm based on partition sort. This paradigm of measuring efficiency of algorithms looks promising for further interesting applications beyond the existing ones. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2506_08261 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Towards universally optimal sorting algorithms Sen, Sandeep Data Structures and Algorithms Computational Complexity F.2.2 We formalize a new paradigm for optimality of algorithms, that generalizes worst-case optimality based only on input-size to problem-dependent parameters including implicit ones. We re-visit some existing sorting algorithms from this perspective, and also present a novel measure of sortedness that leads to an optimal algorithm based on partition sort. This paradigm of measuring efficiency of algorithms looks promising for further interesting applications beyond the existing ones. |
| title | Towards universally optimal sorting algorithms |
| topic | Data Structures and Algorithms Computational Complexity F.2.2 |
| url | https://arxiv.org/abs/2506.08261 |