The cache-oblivious distribution sort is a comparison-based sorting algorithm. It is similar to quicksort, but it is a cache-oblivious algorithm, designed for a setting where the number of elements to sort is too large to fit in a cache where operations are done. 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 .
Attributes | Values |
---|---|
rdf:type |
|
rdfs:label |
|
rdfs:comment |
|
dcterms:subject | |
Wikipage page ID |
|
Wikipage revision ID |
|
Link from a Wikipage to another Wikipage | |
Link from a Wikipage to an external page | |
sameAs | |
dbp:wikiPageUsesTemplate | |
has abstract |
|
prov:wasDerivedFrom | |
page length (characters) of wiki page |
|
foaf:isPrimaryTopicOf | |
is Link from a Wikipage to another Wikipage of | |
is foaf:primaryTopic of |