Merge algorithms are a family of algorithms that run sequentially over multiple sorted lists, typically producing more sorted lists as output. This is wellsuited for machines with tape drives. Use has declined due to large random access memories, and many applications of merge algorithms have faster alternatives when a randomaccess memory is available.
The general merge algorithm has a set of pointers p_{0..n} that point to positions in a set of lists L_{0..n}. Initially they point to the first item in each list. The algorithm is as follows:
While any of p_{0..n} still point to data inside of L_{0..n} instead of past the end:
Merge algorithms generally run in time proportional to the sum of the lengths of the lists; merge algorithms that operate on large numbers of lists at once will multiply the sum of the lengths of the lists by the time to figure out which of the pointers points to the lowest item, which can be accomplished with a heapbased priority queue in O(log n) time, for O(m log n) time, where n is the number of lists being merged and m is the sum of the lengths of the lists. When merging two lists of length m, there is a lower bound of 2m − 1 comparisons required in the worst case.
The classic merge (the one used in merge sort) 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.
In parallel computing, arrays of sorted values may be merged efficiently using an all nearest smaller values computation.^{[1]}
The C++'s Standard Template Library has
the function std::merge
, which merges two sorted
ranges of iterators, and std::inplace_merge
, which
merges two consecutive sorted ranges inplace. In
addition, the std::list
(linked list) class has its
own merge
method which merges another list into
itself. The type of the elements merged must support the lessthan
(<) operator, or it must be provided with a custom
comparator.
