#jsDisabledContent { display:none; } My Account |  Register |  Help

Merge algorithm

Article Id: WHEBN0000020362
Reproduction Date:

 Title: Merge algorithm Author: World Heritage Encyclopedia Language: English Subject: Collection: Publisher: World Heritage Encyclopedia Publication Date:

Merge algorithm

Merge algorithms are a family of algorithms that run sequentially over multiple sorted lists, typically producing more sorted lists as output. This is well-suited for machines with tape drives.

The general merge algorithm has a set of pointers p0..n that point to positions in a set of lists L0..n. Initially they point to the first item in each list. The algorithm is as follows:

While any of p0..n still point to data inside of L0..n instead of past the end:

1. do something with the data items p0..n point to in their respective lists
2. find out which of those pointers points to the item with the lowest key; advance one of those pointers to the next item in its list

Analysis

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 heap-based 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.

Language support

Some computer languages provide build-in merge support for collections.

C++

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 in-place. 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 less-than (<) operator, or it must be provided with a custom comparator.

Python

Python (programming language)'s standard library (since 2.6) also has a `merge()` function in the `heapq` module, that takes multiple sorted iterables, and merges them into a single iterator.[1]

C#

In C#, merge can be achieved with LINQ.

Parallel merge

In parallel computing, arrays of sorted values may be merged efficiently using an all nearest smaller values computation.[2]

Parallel merge can also be implemented using a divide-and-conquer algorithm, developed and shown in pseudo-code in.[3] This algorithm performs well when combined with a fast sequential merge as a base case for merging of small arrays. Implementation using Intel's Threading Building Blocks (TBB) and Microsoft's Parallel Pattern Library (PPL) to run on multi-core processors is shown to perform well in practice.[4]

Notes

1. ^ https://docs.python.org/library/heapq.html#heapq.merge
2. ^ Berkman, Omer; Schieber, Baruch;
3. ^ Cormen et al. 2009, p. 800
4. ^ V. J. Duvanenko, "Parallel Merge", Dr. Dobb's Journal, February 2011

References

• Donald Knuth. The Art of Computer Programming, Volume 3: Sorting and Searching, Third Edition. Addison-Wesley, 1997. ISBN 0-201-89685-0. Pages 158–160 of section 5.2.4: Sorting by Merging. Section 5.3.2: Minimum-Comparison Merging, pp. 197–207.
This article was sourced from Creative Commons Attribution-ShareAlike License; additional terms may apply. World Heritage Encyclopedia content is assembled from numerous content providers, Open Access Publishing, and in compliance with The Fair Access to Science and Technology Research Act (FASTR), Wikimedia Foundation, Inc., Public Library of Science, The Encyclopedia of Life, Open Book Publishers (OBP), PubMed, U.S. National Library of Medicine, National Center for Biotechnology Information, U.S. National Library of Medicine, National Institutes of Health (NIH), U.S. Department of Health & Human Services, and USA.gov, which sources content from all federal, state, local, tribal, and territorial government publication portals (.gov, .mil, .edu). Funding for USA.gov and content contributors is made possible from the U.S. Congress, E-Government Act of 2002.

Crowd sourced content that is contributed to World Heritage Encyclopedia is peer reviewed and edited by our editorial staff to ensure quality scholarly research articles.