Block sort, or block merge sort, is a sorting algorithm that combines at least two merge operations with an insertion sort to achieve O(n log n) in-place, stable sorting time. It takes its name from the observation that merging two sorted lists is equivalent to breaking one list into evenly sized blocks, inserting each block into the other list under special rules, and then merging the resulting pairs of blocks; one practical algorithm for O(n log n) in-place merging along these lines was proposed by Pok-Son Kim and Arne Kutzner in 2008.
Facts
Time Complexity
Time Complexity (category)Linearithmic Time -- O(n log n) 1 Connections
In Field
Source Block sort (Wikipedia)
Sources
1. Wikidata: Block Sort
- Wikidata Q17019833, class allow-list match (w-wdresolver-0926)
- Wikipedia Block sort infobox time O(n log n)
View the SourceBlock sort (Wikipedia)
In Field: Algorithms and Complexity Theory, Lead section
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) (see Big O notation) in-place stable sorting time.
In Group: Comparison Sorting Algorithms, Lead
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) (see Big O notation) in-place stable sorting time.
View the SourceReader Challenges (0)
No disputes yet. Spotted an error or a better source? Open the first one.
Sign in to dispute this or suggest a correction.