Merge algorithm

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. Use has declined due to large random access memories, and many applications of merge algorithms have faster alternatives when a random-access memory is available.[citation needed]

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

Contents

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

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 (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]

Parallel Merge

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

Parallel merge can also be implemented using a divide-and-conquer algorithm, developed and shown in pseudo-code in.[2] 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.[3]

References

  1. ^ Berkman, Omer; Schieber, Baruch; Vishkin, Uzi (1993), "Optimal double logarithmic parallel algorithms based on finding all nearest smaller values", Journal of Algorithms 14 (3): 344–370, doi:10.1006/jagm.1993.1018 .
  2. ^ Cormen, Thomas; Leiserson, Charles; Stein, Ronald, Introduction to Algorithms (Third Edition, MIT Press and McGraw-Hill, 2009 ed.), p. 800 .
  3. ^ V. J. Duvanenko, "Parallel Merge", Dr. Dobb's Journal, February 2011

Wikimedia Foundation. 2010.

Игры ⚽ Нужен реферат?

Look at other dictionaries:

  • Package-merge algorithm — The Package Merge Algorithm is an O(nL) time algorithm for finding anoptimal length limited Huffman code for a given distribution on a given alphabet of size n , where no code word is longer than L . It is a greedy algorithm, and a generalization …   Wikipedia

  • Merge sort — Example of merge sort sorting a list of random dots. Class Sorting algorithm Data structure Array Worst case performance O(n log n) …   Wikipedia

  • Merge (revision control) — Merging (also called integration) in revision control, is a fundamental operation that reconciles multiple changes made to a revision controlled collection of files. Most often, it is necessary when a file is modified by two people on two… …   Wikipedia

  • Merge — See Help:Merging for the usage of Merge in Wikipedia. Contents 1 Concepts 2 Computer science 3 Music …   Wikipedia

  • Algorithm — Flow chart of an algorithm (Euclid s algorithm) for calculating the greatest common divisor (g.c.d.) of two numbers a and b in locations named A and B. The algorithm proceeds by successive subtractions in two loops: IF the test B ≤ A yields yes… …   Wikipedia

  • Sort-merge join — The Sort Merge Join (also known as Merge Join) is an example of a join algorithm and is used in the implementation of a relational database management system. The basic problem of a join algorithm is to find, for each distinct value of the join… …   Wikipedia

  • Ramer–Douglas–Peucker algorithm — The Douglas–Peucker algorithm is an algorithm for reducing the number of points in a curve that is approximated by a series of points. The initial form of the algorithm was independently suggested in 1972 by Urs Ramer and 1973 by David Douglas… …   Wikipedia

  • Sorting algorithm — In computer science, a sorting algorithm is an algorithm that puts elements of a list in a certain order. The most used orders are numerical order and lexicographical order. Efficient sorting is important for optimizing the use of other… …   Wikipedia

  • Nearest-neighbor chain algorithm — In the theory of cluster analysis, the nearest neighbor chain algorithm is a method that can be used to perform several types of agglomerative hierarchical clustering, using an amount of memory that is linear in the number of points to be… …   Wikipedia

  • Nondeterministic algorithm — In computer science, a nondeterministic algorithm is an algorithm that can exhibit different behaviors on different runs, as opposed to a deterministic algorithm. There are several ways an algorithm may behave differently from run to run. A… …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”