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.

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:

1. do something with the data items p_0..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