K-way merge algorithms, or multiway merges, are sequence merge algorithms that specialize in taking k sorted lists and merging them into a single sorted list, generalizing the simpler two list binary merge case. K-way merging is also used as a step within external sorting, where data too large to fit in memory is sorted by first creating many small sorted runs and then merging them together.
Facts
Time Complexity
Time Complexity (category)Linearithmic Time -- O(n log n) 1 Sources
1. K-way merge algorithm (Wikipedia)
Wikipedia article body, read for Browse By backfill (w-bbfill-computing6-0927)
NIST Dictionary of Algorithms and Data Structures: k-way merge
NIST Dictionary of Algorithms and Data StructuresIn Group: Comparison Sorting Algorithms, DefinitionQuote, In Group: Comparison Sorting Algorithms, Definition
Combine k sorted data streams into a single sorted stream.
Reader 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.