• Facets (new session)
• Description
• Metadata
• Settings
  • Rule: ActivityStreamsMapasEquivalentb3sb3sifpdbprdf-labelfacetshttp://dbpedia.org/resource/inference/rules/dbpedia#http://dbpedia.org/resource/inference/rules/opencyc#http://dbpedia.org/resource/inference/rules/umbel#http://dbpedia.org/resource/inference/rules/yago#http://dbpedia.org/schema/property_rules#http://www.ontologyportal.org/inference/rules/SUMO#http://www.ontologyportal.org/inference/rules/WordNet#http://www.w3.org/2002/07/owl#ldpoplwebskos-transurn:det:rdf:labelvirtrdf-labelvirtrdf-urlNone
    
  • Inverse Functional Properties: Disabled (fastest) Apply to subjects only Apply to objects only Apply to both subjects and objects
  • "Same As": Disabled (fastest) Apply to subjects only Apply to objects only Apply to both subjects and objects (recommended) Apply to subjects, objects and predicates (not recommended on big datasets) Apply to predicates only (special use cases only)

About: Cache-oblivious distribution sort     Goto   Sponge   NotDistinct   Permalink

An Entity of Type : yago:WikicatExternalMemoryAlgorithms, within Data Space : dbpedia.org associated with source document(s)

Type: yago:WikicatComparisonSortsyago:WikicatSortingAlgorithmsyago:Abstraction100002137yago:Act100030358yago:Activity100407535yago:Algorithm105847438yago:Category105838765yago:Cognition100023271yago:Concept105835747yago:Content105809192yago:Event100029378yago:Idea105833840yago:Kind105839024yago:Procedure101023820yago:PsychologicalFeature100023100yago:YagoPermanentlyLocatedEntityyago:Rule105846932yago:SortingAlgorithm105847658yago:WikicatExternalMemoryAlgorithms New Facet based on Instances of this Class

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 .