In computer science, k-way merge algorithms or multiway merges are a specific type of 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 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 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 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 {\displaystyle k\leq n} , which simplifies the reported running times. The problem can be solved in O ( n ⋅ log ( k ) ) {\displaystyle {\mathcal {O}}(n\cdot \log(k))} running time with O ( n ) {\displaystyle {\mathcal {O}}(n)} space. Several algorithms that achieve this running time exist.
Iterative 2-way merge The problem can be solved 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) 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 + k log k) running time.
Direct k-way merge In this case, we would simultaneously merge k-runs together. 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). The heap is more commonly used, although a tournament tree is faster in practice. A heap uses approximately 2*log(k) comparisons in each step because it handles the tree from the root down to the bottom and needs to compare both children of each node. Meanwhile, a tournament tree only needs log(k) comparisons because it starts on the bottom of the tree and works up to the root, only making a single comparison in each layer. The tournament tree should therefore be the preferred implementation.
Heap The idea is to maintain a min-heap of the k lists, each keyed by their smallest current element. A simple algorithm builds an output buffer with nodes from the heap. Start by building a min-heap of nodes, where each node consists of a head element of the list, and the rest (or tail) of the list. Because the lists are sorted initially, the head is the smallest element of each list; the heap property guarantees that the root contains the minimum element over all lists. Extract the root node from the heap, add the head element to the output buffer, create a new node out of the tail, and insert it into the heap. Repeat until there is only one node left in the heap, at which point just append that remaining list (head and tail) to the output buffer. Using pointers, an in-place heap algorithm
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 increase 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 increase-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
… excerpt ends here. Continue reading the full article.
