k-way merge algorithm

From Wikipedia, the free encyclopedia
Jump to navigation Jump to search


In computer science, k-way merge algorithms or multiway merges are a specific type of sequence merge algorithms that specialize in taking in multiple 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. 2-way merges are also referred to as binary merges.

2-way merge[edit]

A 2-way merge, or a binary merge, has been studied extensively due to its key role in merge sort. An example of such is the classic merge that appears frequently in merge sort examples. The classic merge outputs the data item with the lowest key at each step; given some sorted lists, it produces a sorted list containing all the elements in any of the input lists, and it does so in time proportional to the sum of the lengths of the input lists.

Denote by A[1..p] and B[1..q] two arrays sorted in increasing order. Further, denote by C[1..n] the output array. The canonical 2-Way merge algorithm[1] stores indices i, j, and k into A, B, and C respectively. Initially, these indices refer to the first element, i.e., are 1. If A[i] < B[j], then the algorithm copies A[i] into C[k] and increases i and k. Otherwise, the algorithm copies B[j] into C[k] and increases j and k. A special case arises if either i or j have reached the end of A or B. In this case the algorithm copies the remaining elements of B or A into C and terminates.

k-way merge[edit]

The k-way merge problem consists of merging k sorted arrays to produce a single sorted array with the same elements. Denote by n the total number of elements. 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. As a consequence k < n, which simplifies the reported running times. The problem can be solved in O(n log k) running time with O(n) space. Several algorithms that achieve this running time exist.

Iterative 2-Way merge[edit]

The problem can be merged by iteratively merging two of the k arrays using a 2-way merge until only a single array is left. If the arrays are merged in arbitrary order, then the resulting running time is only O(kn). This is suboptimal.

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) iteration. 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.

Direct k-way merge[edit]

The basic idea of a direct k-way merge consists of efficiently computing the minimum element of all k arrays and then transferring it to the output array.

A straightforward implementation would scan all k arrays to determine the minimum. This straightforward implementation results in a running time of Θ(kn). Note that this is mentioned only as a possibility, for the sake of discussion. Although it would work it is not efficient.

We can improve upon this by computing the smallest element faster. By using either heaps, tournament trees, or splay trees, the smallest element can be determined in O(log k) time. The resulting running times are therefore in O(n log k).

Heap[edit]

The heap algorithm [2] allocates a min-heap of pointers into the input arrays. Initially these pointers point to the smallest elements of the input array. The pointers are sorted by the value that they point to. In an O(k) preprocessing step the heap is created using the standard heapify procedure. Afterwards, the algorithm iteratively transfers the element that the root pointer points to, increases this pointer and executes the standard decrease key procedure upon the root element. The running time of the increase key procedure is bounded by O(log k). As there are n elements, the total running time is O(n log k).

Note that the operation of replacing the key and iteratively doing decrease-key or sift-down are not supported by many Priority Queue libraries such as C++ stl and Java. Doing an extract-min and insert function is less efficient.

Tournament Tree[edit]

The tournament tree[3] algorithm constructs a balanced binary tree with k leaves. Every leaf stores a pointer to one of the input arrays. Every node stores a value and an index. For the i-th leaf the value is the value that its pointer points to and the index is i. For every internal leaf the value is the minimum of the values of the node's children. The index of an internal leaf indicates which input array the value comes from. The root of the tournament tree contains the smallest element and the index of the corresponding input array. The algorithm iteratively transfers this element and advances the corresponding pointer. It then updates the values of the nodes on the path from the corresponding leaf to the root. As the tree is balanced, this path contains only Θ(log k) elements. As there are n elements that need to be extracted, the resulting total running time is Θ(n log k).

Example[edit]

Suppose we have 4 sorted arrays:

{5, 10, 15, 20}

{10, 13, 16, 19}

{2, 19, 26, 40}

{18, 22, 23, 24}

We start with the heads of each array and then build a binary tree from there.

Binary Ideal Merge 1.png

The nodes from each array are compared to each other, before the value 2 is found as the lowest list head element. That value is then popped off, and its leaf is refilled with the next value in the list.

Binary Ideal Merge 2.png

The value 2 is repopulated by the next value in the sorted list, 19. The comparisons end with 5 being the smallest value, and thus the next value to be popped off. This continues until all of the sorted lists are empty.

Lower Running Time Bound[edit]

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. (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[edit]

k-way merges are used in external sorting procedures.[4] 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 merges 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.

References[edit]

  1. ^ Thomas H. Cormen; Charles E. Leiserson; Ronald L. Rivest; Clifford Stein (2001). Introduction To Algorithms. MIT Press. pp. 28–29. ISBN 978-0-262-03293-3. 
  2. ^ Bentley, Jon Louis (2000). Programming Pearls (2nd ed.). Addison Wesley. pp. 147–162. ISBN 0201657880. 
  3. ^ Knuth, Donald (1998). "Chapter 5.4.1. Multiway Merging and Replacement Selection". Sorting and Searching. The Art of Computer Programming. 3 (2nd ed.). Addison-Wesley. pp. 158–168. ISBN 0-201-89685-0. 
  4. ^ Shaffer, Clifford A. (2012-07-26). Data Structures and Algorithm Analysis in C++, Third Edition. Courier Corporation. ISBN 9780486172620.