About: Cache-oblivious distribution sort

Facets (new session)
Description
Metadata
Settings
- Rule:
- Inverse Functional Properties:
- "Same As":

About: Cache-oblivious distribution sort Goto Sponge NotDistinct Permalink

An Entity of Type : owl:Thing, within Data Space : el.dbpedia.org associated with source document(s)

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
rdfs:label	Cache-oblivious distribution sort (en)
rdfs:comment	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 . (en)
sameAs	Cache-oblivious distribution sort Cache-oblivious distribution sort
dbp:wikiPageUsesTemplate	dbt:Multiple_issues dbt:Not_a_typo dbt:Primary_sources dbt:Short_description dbt:Technical
Subject	Analysis of algorithms Cache (computing) Comparison sorts Sorting algorithms Models of computation External memory algorithms
Link from a Wikipage to an external page	http://supertech.csail.mit.edu/papers/Prokop99.pdf
prov:wasDerivedFrom	http://en.wikipedia.org/wiki/Cache-oblivious_distribution_sort?oldid=928188122&ns=0
Wikipage page ID	42794826 (xsd:integer)
page length (characters) of wiki page	5972 (xsd:nonNegativeInteger)
Wikipage revision ID	928188122 (xsd:integer)
Link from a Wikipage to another Wikipage	Cache-oblivious algorithm Cache (computing) Analysis of algorithms Cache (computing) Comparison sorts Sorting algorithms Models of computation Sorting algorithm Comparison sort External memory algorithms Funnelsort External memory algorithm External sorting Median of medians Quicksort
has abstract	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 . (en)
foaf:isPrimaryTopicOf	http://en.wikipedia.org/wiki/Cache-oblivious_distribution_sort
is Link from a Wikipage to another Wikipage of	Cache-oblivious algorithm Funnelsort External sorting
is foaf:primaryTopic of	http://en.wikipedia.org/wiki/Cache-oblivious_distribution_sort

Faceted Search & Find service v1.17_git151 as of Feb 20 2025

Alternative Linked Data Documents: ODE Content Formats:

RDF

ODATA

Microdata

About

OpenLink Virtuoso version 07.20.3240 as of Nov 11 2024, on Linux (x86_64-ubuntu_focal-linux-gnu), Single-Server Edition (72 GB total memory, 1 GB memory in use)
Data on this page belongs to its respective rights holders.
Virtuoso Faceted Browser Copyright © 2009-2025 OpenLink Software