Cache-oblivious distribution sort
The cache-oblivious distribution sort is a comparison-based sorting algorithm. It was introduced in 1999 in the context of the cache oblivious model. In the external memory model, the number of memory transfers it needs to perform a sort of items on a machine with cache of size and cache lines of length is , under the tall cache assumption that . This number of memory transfers has been shown to be asymptotically optimal for comparison sorts. This distribution sort also achieves the asymptotically optimal runtime complexity of .
primaryTopic
Cache-oblivious distribution sort
The cache-oblivious distribution sort is a comparison-based sorting algorithm. It was introduced in 1999 in the context of the cache oblivious model. In the external memory model, the number of memory transfers it needs to perform a sort of items on a machine with cache of size and cache lines of length is , under the tall cache assumption that . This number of memory transfers has been shown to be asymptotically optimal for comparison sorts. This distribution sort also achieves the asymptotically optimal runtime complexity of .
has abstract
The cache-oblivious distributi ...... ptimal runtime complexity of .
@en
Link from a Wikipage to an external page
Wikipage page ID
42,794,826
Wikipage revision ID
610,270,738
subject
comment
The cache-oblivious distributi ...... ptimal runtime complexity of .
@en
label
Cache-oblivious distribution sort
@en