HomePage | Recent Changes | Preferences

Merge is a family of algorithms that run sequentially over multiple sorted lists, typically producing more sorted lists as output. This makes them great for machines with tape drives. They're not as widely-used as they used to be, because now we have large random access memories, and many applications of merge algorithms have faster alternatives when you have a random-access memory that holds all your data.

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

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(lg n) time, for O(m lg n) time (where m is the sum of the lengths of the lists).

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.

Merge can also be used for a variety of other things:

HomePage | Recent Changes | Preferences
This page is read-only | View other revisions
Last edited December 12, 2001 7:30 am by Taw (diff)