K-way merge algorithm - Revision history

LR.127: Adding local short description: "Sequence merge algorithm in computer science", overriding Wikidata description "type of merge algorithm"

2024-11-08T01:39:15Z

Adding local short description: "Sequence merge algorithm in computer science", overriding Wikidata description "type of merge algorithm"

← Previous revision		Revision as of 01:39, 8 November 2024
Line 1:		Line 1:
			{{Short description\|Sequence merge algorithm in computer science}}
	{{DISPLAYTITLE:''k''-way merge algorithm}}		{{DISPLAYTITLE:''k''-way merge algorithm}}
	In [[computer science]], '''''k''-way merge algorithms''' or multiway merges are a specific type of [[Merge algorithm\|sequence merge algorithms]] that specialize in taking in k sorted lists and merging them into a single sorted list. These merge algorithms generally refer to merge algorithms that take in a number of sorted lists greater than two. Two-way merges are also referred to as binary merges. The k-way merge is also an external sorting algorithm.		In [[computer science]], '''''k''-way merge algorithms''' or multiway merges are a specific type of [[Merge algorithm\|sequence merge algorithms]] that specialize in taking in k sorted lists and merging them into a single sorted list. These merge algorithms generally refer to merge algorithms that take in a number of sorted lists greater than two. Two-way merges are also referred to as binary merges. The k-way merge is also an external sorting algorithm.

Lesseasyway: Spelling/grammar/punctuation/typographical correction

2024-09-03T21:32:36Z

Spelling/grammar/punctuation/typographical correction

← Previous revision		Revision as of 21:32, 3 September 2024
Line 1:		Line 1:
	{{DISPLAYTITLE:''k''-way merge algorithm}}		{{DISPLAYTITLE:''k''-way merge algorithm}}
	In [[computer science]], '''''k''-way merge algorithms''' or multiway merges are a specific type of [[Merge algorithm\|sequence merge algorithms]] that specialize in taking in k sorted lists and merging them into a single sorted list. These merge algorithms generally refer to merge algorithms that take in a number of sorted lists greater than two. Two-way merges are also referred to as binary merges.The k- way merge is also an external sorting algorithm.		In [[computer science]], '''''k''-way merge algorithms''' or multiway merges are a specific type of [[Merge algorithm\|sequence merge algorithms]] that specialize in taking in k sorted lists and merging them into a single sorted list. These merge algorithms generally refer to merge algorithms that take in a number of sorted lists greater than two. Two-way merges are also referred to as binary merges. The k-way merge is also an external sorting algorithm.

	== Two-way merge ==		== Two-way merge ==

Citation bot: Altered author-link. | Use this bot. Report bugs. | Suggested by Abductive | Category:Sorting algorithms | #UCB_Category 11/48

2024-06-10T21:45:03Z

Altered author-link. | Use this bot. Report bugs. | Suggested by Abductive | Category:Sorting algorithms | #UCB_Category 11/48

← Previous revision		Revision as of 21:45, 10 June 2024
Line 53:		Line 53:
	\|last1=Bentley		\|last1=Bentley
	\|first1=Jon Louis		\|first1=Jon Louis
	\|author-link=~~Jon_Bentley_~~(~~computer_scientist~~)		\|author-link=Jon Bentley (computer scientist)
	\|title=Programming Pearls		\|title=Programming Pearls
	\|date=2000		\|date=2000

Geomatrist: minor grammatical error fix

2024-04-04T04:06:41Z

minor grammatical error fix

← Previous revision		Revision as of 04:06, 4 April 2024
Line 1:		Line 1:
	{{DISPLAYTITLE:''k''-way merge algorithm}}		{{DISPLAYTITLE:''k''-way merge algorithm}}
	In [[computer science]], '''''k''-way merge algorithms''' or multiway merges are a specific type of [[Merge algorithm\|sequence merge algorithms]] that specialize in taking in k sorted lists and merging them into a single sorted list. These merge algorithms generally refer to merge algorithms that take in a number of sorted lists greater than two. Two-way merges are also referred to as binary merges.The k- way merge also external sorting algorithm.		In [[computer science]], '''''k''-way merge algorithms''' or multiway merges are a specific type of [[Merge algorithm\|sequence merge algorithms]] that specialize in taking in k sorted lists and merging them into a single sorted list. These merge algorithms generally refer to merge algorithms that take in a number of sorted lists greater than two. Two-way merges are also referred to as binary merges.The k- way merge is also an external sorting algorithm.

	== Two-way merge ==		== Two-way merge ==

Frap: /* Lower bound on running time */

2024-03-08T15:02:24Z

Lower bound on running time

← Previous revision		Revision as of 15:02, 8 March 2024
Line 163:		Line 163:
	=== Lower bound on running time ===		=== Lower bound on running time ===

	One can show that no comparison-based ''k''-way merge algorithm exists with a running time in O(n f(k)) where f grows asymptotically slower than a logarithm, and n being the total number of elements.		One can show that no comparison-based ''k''-way merge algorithm exists with a running time in ''O''(''n'' f(k)) where f grows asymptotically slower than a logarithm, and n being the total number of elements. (Excluding data with desirable distributions such as disjoint ranges.) The proof is a straightforward reduction from comparison-based sorting. Suppose that such an algorithm existed, then we could construct a comparison-based sorting algorithm with running time ''O''(''n'' f(''n'')) as follows: Chop the input array into n arrays of size 1. Merge these n arrays with the ''k''-way merge algorithm. The resulting array is sorted and the algorithm has a running time in ''O''(''n'' f(''n'')). This is a contradiction to the well-known result that no comparison-based sorting algorithm with a worst case running time below ''O''(''n'' log ''n'') exists.
	(Excluding data with desirable distributions such as disjoint ranges.)
	The proof is a straightforward reduction from comparison-based sorting.
	Suppose that such an algorithm existed, then we could construct a comparison-based sorting algorithm with running time O(n f(n)) as follows:
	Chop the input array into n arrays of size 1.
	Merge these n arrays with the ''k''-way merge algorithm.
	The resulting array is sorted and the algorithm has a running time in O(n f(n)).
	This is a contradiction to the well-known result that no comparison-based sorting algorithm with a worst case running time below O(n log n) exists.

	== External sorting ==		== External sorting ==

Dancing Dollar: clean up, typo(s) fixed: … → ... (2)

2023-04-30T14:21:48Z

clean up, typo(s) fixed: … → ... (2)

← Previous revision		Revision as of 14:21, 30 April 2023
Line 40:		Line 40:

	We can improve upon this by computing the smallest element faster.		We can improve upon this by computing the smallest element faster.
	By using either [[Heap (data structure)\|heaps]], tournament trees, or [[~~Splay_tree\|~~splay ~~trees~~]], the smallest element can be determined in O(log k) time.		By using either [[Heap (data structure)\|heaps]], tournament trees, or [[splay tree]]s, the smallest element can be determined in O(log k) time.
	The resulting running times are therefore in O(n log k).		The resulting running times are therefore in O(n log k).

Line 90:		Line 90:
	When one of the leaves is updated, all games from the leaf to the root are replayed. In the following [[pseudocode]], an object oriented tree is used instead of an array because it is easier to understand. Additionally, the number of lists to merge is assumed to be a power of two.		When one of the leaves is updated, all games from the leaf to the root are replayed. In the following [[pseudocode]], an object oriented tree is used instead of an array because it is easier to understand. Additionally, the number of lists to merge is assumed to be a power of two.

	'''function''' merge(L1, …, Ln)		'''function''' merge(L1, ..., Ln)
	buildTree(heads of L1, …, Ln)		buildTree(heads of L1, ..., Ln)
	'''while''' tree has elements		'''while''' tree has elements
	winner := tree.winner		winner := tree.winner
Line 120:		Line 120:
	===== Running time =====		===== Running time =====

	In the beginning, the tree is first created in time Θ(k). In each step of merging, only the games on the path from the new element to the root need to be replayed. In each layer, only one comparison is needed. As the tree is balanced, the path from one of the input arrays to the root contains only Θ(log k) elements. In total, there are n elements that need to be transferred. The resulting total running time is therefore in Θ(n log k). <ref name="knuth98" />		In the beginning, the tree is first created in time Θ(k). In each step of merging, only the games on the path from the new element to the root need to be replayed. In each layer, only one comparison is needed. As the tree is balanced, the path from one of the input arrays to the root contains only Θ(log k) elements. In total, there are n elements that need to be transferred. The resulting total running time is therefore in Θ(n log k).<ref name="knuth98" />

	===== Example =====		===== Example =====

Ammulya at 17:35, 19 April 2023

2023-04-19T17:35:44Z

← Previous revision		Revision as of 17:35, 19 April 2023
Line 1:		Line 1:
	{{DISPLAYTITLE:''k''-way merge algorithm}}		{{DISPLAYTITLE:''k''-way merge algorithm}}
	In [[computer science]], '''''k''-way merge algorithms''' or multiway merges are a specific type of [[Merge algorithm\|sequence merge algorithms]] that specialize in taking in k sorted lists and merging them into a single sorted list. These merge algorithms generally refer to merge algorithms that take in a number of sorted lists greater than two. Two-way merges are also referred to as binary merges.		In [[computer science]], '''''k''-way merge algorithms''' or multiway merges are a specific type of [[Merge algorithm\|sequence merge algorithms]] that specialize in taking in k sorted lists and merging them into a single sorted list. These merge algorithms generally refer to merge algorithms that take in a number of sorted lists greater than two. Two-way merges are also referred to as binary merges.The k- way merge also external sorting algorithm.

	== Two-way merge ==		== Two-way merge ==

Uurtamo: /* External sorting */

2023-01-04T19:42:34Z

External sorting

← Previous revision		Revision as of 19:42, 4 January 2023
Line 176:		Line 176:
	''k''-way merges are used in external sorting procedures.<ref>{{Cite book\|title = Data Structures and Algorithm Analysis in C++, Third Edition\|url = https://books.google.com/books?id=AijEAgAAQBAJ\|publisher = Courier Corporation\|date = 2012-07-26\|isbn = 9780486172620\|first = Clifford A.\|last = Shaffer}}</ref> [[External sorting\|External sorting algorithms]] are a class of sorting algorithms that can handle massive amounts of data. External sorting is required when the data being sorted do not fit into the main memory of a computing device (usually RAM) and instead they must reside in the slower external memory (usually a hard drive). ''k''-way merge algorithms usually take place in the second stage of external sorting algorithms, much like they do for merge sort.		''k''-way merges are used in external sorting procedures.<ref>{{Cite book\|title = Data Structures and Algorithm Analysis in C++, Third Edition\|url = https://books.google.com/books?id=AijEAgAAQBAJ\|publisher = Courier Corporation\|date = 2012-07-26\|isbn = 9780486172620\|first = Clifford A.\|last = Shaffer}}</ref> [[External sorting\|External sorting algorithms]] are a class of sorting algorithms that can handle massive amounts of data. External sorting is required when the data being sorted do not fit into the main memory of a computing device (usually RAM) and instead they must reside in the slower external memory (usually a hard drive). ''k''-way merge algorithms usually take place in the second stage of external sorting algorithms, much like they do for merge sort.

	A multiway merge allows for the files outside of memory to be merged in fewer passes than in a binary merge. If there are 6 runs that need be merged then a binary merge would need to take 3 merge passes, as opposed to a 6-way merge's single merge pass. This reduction of merge passes is especially important considering the large amount of information that is usually being sorted in the first place, allowing for greater speed-ups while also reducing the amount of accesses to slower ~~memory~~.		A multiway merge allows for the files outside of memory to be merged in fewer passes than in a binary merge. If there are 6 runs that need be merged then a binary merge would need to take 3 merge passes, as opposed to a 6-way merge's single merge pass. This reduction of merge passes is especially important considering the large amount of information that is usually being sorted in the first place, allowing for greater speed-ups while also reducing the amount of accesses to slower storage.

	== References ==		== References ==

138.75.209.124: /* k-way merge */k can be equal to n when all arrays are 1 element each

2021-10-02T21:46:51Z

k-way merge: k can be equal to n when all arrays are 1 element each

← Previous revision		Revision as of 21:46, 2 October 2021
Line 19:		Line 19:
	n is equal to the size of the output array and the sum of the sizes of the k input arrays.		n is equal to the size of the output array and the sum of the sizes of the k input arrays.
	For simplicity, we assume that none of the input arrays is empty.		For simplicity, we assume that none of the input arrays is empty.
	As a consequence <math>k < n</math>, which simplifies the reported running times.		As a consequence <math>k \le n</math>, which simplifies the reported running times.
	The problem can be solved in <math>\mathcal{O}(n \cdot \log(k))</math> running time with <math>\mathcal{O}(n)</math> space.		The problem can be solved in <math>\mathcal{O}(n \cdot \log(k))</math> running time with <math>\mathcal{O}(n)</math> space.
	Several algorithms that achieve this running time exist.		Several algorithms that achieve this running time exist.

138.75.209.124: /* Iterative 2-way merge */added time to merge k-1 arrays with 1 element each

2021-10-02T21:38:57Z

Iterative 2-way merge: added time to merge k-1 arrays with 1 element each

← Previous revision		Revision as of 21:38, 2 October 2021
Line 29:		Line 29:
	The running time can be improved by iteratively merging the first with the second, the third with the fourth, and so on. As the number of arrays is halved in each iteration, there are only Θ(log k) iterations. In each iteration every element is moved exactly once. The running time per iteration is therefore in Θ(n) as n is the number of elements. The total running time is therefore in Θ(n log k).		The running time can be improved by iteratively merging the first with the second, the third with the fourth, and so on. As the number of arrays is halved in each iteration, there are only Θ(log k) iterations. In each iteration every element is moved exactly once. The running time per iteration is therefore in Θ(n) as n is the number of elements. The total running time is therefore in Θ(n log k).

	We can further improve upon this algorithm, by iteratively merging the two shortest arrays. It is clear that this minimizes the running time and can therefore not be worse than the strategy described in the previous paragraph. The running time is therefore in O(n log k). Fortunately, in border cases the running time can be better. Consider for example the degenerate case, where all but one array contain only one element. The strategy explained in the previous paragraph needs Θ(n log k) running time, while the improved one only needs Θ(n) running time.		We can further improve upon this algorithm, by iteratively merging the two shortest arrays. It is clear that this minimizes the running time and can therefore not be worse than the strategy described in the previous paragraph. The running time is therefore in O(n log k). Fortunately, in border cases the running time can be better. Consider for example the degenerate case, where all but one array contain only one element. The strategy explained in the previous paragraph needs Θ(n log k) running time, while the improved one only needs Θ(n + k log k) running time.

	=== Direct ''k''-way merge ===		=== Direct ''k''-way merge ===