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 you have a random-access memory that holds all your data.

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

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

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.

Uses

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

• given a set of current account balances and a set of transactions, both sorted by account number, produce the set of new account balances after the transactions are applied; this requires always advancing the "new transactions" pointer in preference to the "account number" pointer when the two have equal keys, and adding all the numbers on either tape with the same account number to produce the new balance.
• produce a sorted list of records with keys present in all the lists (equijoin); this requires outputting a record whenever the keys of all the p_0..n are equal.
• similarly for finding the largest number on one tape smaller than each number on another tape (e.g. to figure out what tax bracket each person is in).
• similarly for computing set differences: all the records in one list with no corresponding records in another.

Sample implementations

Haskell

merge :: Ord a => [a]->[a]->[a]
merge a [] = a
merge [] b = b
merge (a:as) (b:bs)
	| a <= b     = a : merge as (b:bs)
	| otherwise  = b : merge (a:as) bs

Standard ML

fun merge a [] = a
  | merge [] b = b
  | merge (a as x::xs) (b as y::ys) = if x <= y then
                                        x :: merge xs b 
                                      else
                                        y :: merge a ys;

Python

def merge(a, b):
  if len(a) == 0: return b
  if len(b) == 0: return a
  if a[0] <= b[0]: return a[0:1] + merge(a[1:], b)
  else:            return b[0:1] + merge(a, b[1:])

Ruby

 def merge(a, b)
   c = []
   
   c.push(a[0] <= b[0] ? a.shift : b.shift) until a.empty? or b.empty?
   c + a + b
 end

Common Lisp

(defun mergelists (l1 l2)
  (cond ((null l1) l2)
        ((null l2) l1)
        ((< (car l1) (car l2)) (cons (car l1) (mergelists (cdr l1) l2)))
        (t (cons (car l2) (mergelists l1 (cdr l2))))))

N.B.: The built-in function merge allows for more types and a different comparison operator.

C

void Merge(float v[], int start, int mid, int end) 
{
        int i, j, k;
        float* tmp = malloc(sizeof(float) * (end - start));
        i = start;
        j = mid;
        k = 0;
        while ((i < mid) && (j < end))
        {
                if (v[i] <= v[j])
                        tmp[k++] = v[i++];
                else
                        tmp[k++] = v[j++];
        }
        while (i < mid) 
                tmp[k++] = v[i++];
        while (j < end) 
                tmp[k++] = v[j++];
        for (i = 0; i < (end-start); i++) 
                v[start+i] = tmp[i];
        free(tmp); 
}

C++

The below code is a straight rewrite of the above C implementation (previously billed as C/C++) into a more idiomatic C++ form.

void Merge(float v[], int start, int mid, int end)
{
    int i(start),
        j(mid),
        k(0);
    float * tmp(new float[end - start]);

    while(i < mid && j < end)
    {
        if(v[i] <= v[j])
            tmp[k++] = v[i++];
        else
            tmp[k++] = v[j++];
    }
    while(i < mid) 
        tmp[k++] = v[i++];
    while(j < end) 
        tmp[k++] = v[j++];
    for(i = 0; i < (end - start); ++i) 
        v[start + i] = tmp[i];

    delete[] tmp;
}

Please note that the C++ Standard Template Library provides std::merge to accomplish this task. The library implementation is more efficient and generalized. You should never reinvent the wheel unless you absolutely must.

Java

void Merge(float[] array, int start, int mid, int end) 
{
        int i = start;
        int j = mid;
        int k = 0;
        float[] temp = new float[end - start];
        while ((i < mid) && (j < end))
                if (array[i] <= array[j])
                        temp[k++] = array[i++];
                else 
                        temp[k++] = array[j++];
        while (i < mid) 
                temp[k++] = array[i++];
        while (j < end) 
                temp[k++] = array[j++];
        for (i = start; i < end; i++) 
                array[i] = temp[i - start];
}