SquareSort: a cache-oblivious sorting algorithm
Fuente:
arXiv
Salvato in:
| Autori principali: | , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2024
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866916331356422144 |
|---|---|
| author | Koucký, Michal Matějka, Josef |
| author_facet | Koucký, Michal Matějka, Josef |
| contents | In this paper we consider sorting in the cache-oblivious model of Frigo, Leiserson, Prokop, and Ramachandran (1999). We introduce a new simple sorting algorithm in that model which has asymptotically optimal IO complexity $O(\frac{n}{B} \log_{M/B} n)$, where $n$ is the instance size, $M$ size of the cache and $B$ size of a memory block. This is the same as the complexity of the best known cache-oblivious sorting algorithm FunnelSort. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2407_14801 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | SquareSort: a cache-oblivious sorting algorithm Koucký, Michal Matějka, Josef Data Structures and Algorithms In this paper we consider sorting in the cache-oblivious model of Frigo, Leiserson, Prokop, and Ramachandran (1999). We introduce a new simple sorting algorithm in that model which has asymptotically optimal IO complexity $O(\frac{n}{B} \log_{M/B} n)$, where $n$ is the instance size, $M$ size of the cache and $B$ size of a memory block. This is the same as the complexity of the best known cache-oblivious sorting algorithm FunnelSort. |
| title | SquareSort: a cache-oblivious sorting algorithm |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2407.14801 |