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.
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:
- do something with the data items p0..n point to in their respective lists
- 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
Read more about Merge Algorithm: Analysis, Language Support, Parallel Merge
Famous quotes containing the word merge:
“Traditionally in American society, men have been trained for both competition and teamwork through sports, while women have been reared to merge their welfare with that of the family, with fewer opportunities for either independence or other team identifications, and fewer challenges to direct competition. In effect, women have been circumscribed within that unit where the benefit of one is most easily believed to be the benefit of all.”
—Mary Catherine Bateson (b. 1939)