Merging and set operations

Two sorted rows can become one sorted row without sorting again: keep a finger on the front of each and always take the smaller. Watch the two rows zip together in one pass.

⋯3int merge(const int *a, int m, const int *b, int n, int *out)4{5    int i = 0, j = 0, k = 0;6    while (i < m && j < n) {7        if (a[i] <= b[j])8            out[k++] = a[i++];9        else10            out[k++] = b[j++];11    }12    while (i < m)13        out[k++] = a[i++];14    while (j < n)15        out[k++] = b[j++];16    return k;17}⋯81int main(void)82{83    const int a[5] = { 2, 5, 8, 11, 14 };84    const int b[5] = { 3, 5, 9, 14, 20 };85    int out[10];86    int len = merge(a, 5, b, 5, out);87    print("merge", out, len);88    len = set_union(a, 5, b, 5, out);89    print("union", out, len);90    len = set_intersection(a, 5, b, 5, out);91    print("intersection", out, len);92    len = set_difference(a, 5, b, 5, out);93    print("difference", out, len);94    return 0;95}

Two fingers

Both rows are sorted, so the smallest item of all is at the front of one of them. Take it, move that row’s finger on, and the same is true of what is left. Repeat until one row runs out, then copy the rest of the other: its items are all larger than anything taken so far, and already in order.

Each step takes one item and never looks back, so each finger only moves forward and the whole merge is one pass. Nothing needs sorting afterwards.

The code and its cost

The merge

int merge(const int *a, int m, const int *b, int n, int *out)
{
    int i = 0, j = 0, k = 0;
    while (i < m && j < n) {
        if (a[i] <= b[j])
            out[k++] = a[i++];
        else
            out[k++] = b[j++];
    }
    while (i < m)
        out[k++] = a[i++];
    while (j < n)
        out[k++] = b[j++];
    return k;
}

out[k++] = a[i++]; copies a[i] into out[k], then moves both on: k++ and i++ each give the old value, then add 1. Every item is written once, m + n writes in all. Every comparison writes one item, and the last item is always copied without one, so a merge makes at most m + n − 1 comparisons. Merging the two rows of five took 8.

Ties and stability

The test is a[i] <= b[j]: on a tie, a’s item goes first. Equal items therefore come out in the order of their rows, a’s 5 before b’s 5. A merge that keeps equal items in their original order is stable, which matters when the items are records sorted by one field and equal in it; the sorting chapter relies on it. With <, b’s item would win the tie instead.

Union, intersection and difference

If each row holds a set, sorted and with no repeats, the same walk computes set operations. At each step the front items are either different, and the smaller has no partner in the other row, or equal, and the item is in both.

On the lesson’s rows, the union is 2 3 5 8 9 11 14 20, the intersection 5 14 and the difference 2 8 11; each walk took 7 passes. A pass tests < first and, when that fails, > (the else if), so the 7 passes made 11 comparisons. Unsorted rows would need every pair compared, up to m · n.

Worked example

A merge by hand. Merge 1 4 9 with 2 3 10 12. The comparisons are 1 against 2 (take 1), 4 against 2 (take 2), 4 against 3 (take 3), 4 against 10 (take 4) and 9 against 10 (take 9). The first row is used up after 5 comparisons, and 10 and 12 are copied: 1 2 3 4 9 10 12.

Every pair, against the walk. Finding the intersection of the two lesson rows by comparing each of a’s five items with each of b’s five takes 25 comparisons and gives the same 5 14. The walk took 7 passes and 11 comparisons; it never needs more than 9 passes, so never more than 18 comparisons.

The other difference. b − a, the items of b with no partner in a, is 3 9 20.

Two checks. At most how many comparisons to merge 4 items with 4? (7.) At fewest? (4, when every item of one row is smaller than every item of the other.)

Where it’s used

Merge sort. The sorting chapter sorts by splitting an array in two, sorting each half and merging them, with exactly this loop.

Logs and index files. Sorted files are combined by merging them, one pass each, without loading everything into memory.

Databases and search engines. Two tables sorted on the same key are joined by walking them together; the documents that contain two search words are the intersection of two sorted lists of document numbers.

Reference card

Platform: C11, gcc on x86-64 Linux: int 4 bytes, pointers 8, little-endian. Addresses in the pictures are short stand-ins, by one rule for the whole course; sizes are the real ones.