Location via proxy:   [ UP ]  
[Report a bug]   [Manage cookies]                

About: Block sort

An Entity of Type: Rule105846932, from Named Graph: http://dbpedia.org, within Data Space: dbpedia.org

Block sort, or block merge sort, is a sorting algorithm combining at least two merge operations with an insertion sort to arrive at O(n log n) in-place stable sorting. It gets its name from the observation that merging two sorted lists, A and B, is equivalent to breaking A into evenly sized blocks, inserting each A block into B under special rules, and merging AB pairs. One practical algorithm for O(log n) in place merging was proposed by Pok-Son Kim and Arne Kutzner in 2008.

thumbnail
Property Value
dbo:abstract
  • Block sort, or block merge sort, is a sorting algorithm combining at least two merge operations with an insertion sort to arrive at O(n log n) in-place stable sorting. It gets its name from the observation that merging two sorted lists, A and B, is equivalent to breaking A into evenly sized blocks, inserting each A block into B under special rules, and merging AB pairs. One practical algorithm for O(log n) in place merging was proposed by Pok-Son Kim and Arne Kutzner in 2008. (en)
dbo:thumbnail
dbo:wikiPageID
  • 42275702 (xsd:integer)
dbo:wikiPageLength
  • 36208 (xsd:nonNegativeInteger)
dbo:wikiPageRevisionID
  • 1113865115 (xsd:integer)
dbo:wikiPageWikiLink
dbp:caption
  • Block sort stably sorting numbers 1 to 16. (en)
  • Insertion sort groups of 16, extract two internal buffers, tag the blocks , roll the blocks through , locally merge them, sort the second buffer, and redistribute the buffers. (en)
dbp:class
dbp:data
dbp:wikiPageUsesTemplate
dcterms:subject
rdf:type
rdfs:comment
  • Block sort, or block merge sort, is a sorting algorithm combining at least two merge operations with an insertion sort to arrive at O(n log n) in-place stable sorting. It gets its name from the observation that merging two sorted lists, A and B, is equivalent to breaking A into evenly sized blocks, inserting each A block into B under special rules, and merging AB pairs. One practical algorithm for O(log n) in place merging was proposed by Pok-Son Kim and Arne Kutzner in 2008. (en)
rdfs:label
  • Block sort (en)
owl:differentFrom
owl:sameAs
prov:wasDerivedFrom
foaf:depiction
foaf:isPrimaryTopicOf
is dbo:wikiPageRedirects of
is dbo:wikiPageWikiLink of
is foaf:primaryTopic of
Powered by OpenLink Virtuoso    This material is Open Knowledge     W3C Semantic Web Technology     This material is Open Knowledge    Valid XHTML + RDFa
This content was extracted from Wikipedia and is licensed under the Creative Commons Attribution-ShareAlike 3.0 Unported License