Merging sorted lists

Two sorted chains can become one sorted chain without a single new node. Watch tail zigzag between them.

⋯46struct node *merge_lists(struct node *a, struct node *b)47{48    struct node dummy;49    struct node *tail = &dummy;50    dummy.next = NULL;51    while (a != NULL && b != NULL) {52        comparisons++;53        if (a->key <= b->key) {54            tail->next = a;55            a = a->next;56        } else {57            tail->next = b;58            b = b->next;59        }60        tail = tail->next;61    }62    tail->next = (a != NULL) ? a : b;63    return dummy.next;64}⋯66int main(void)67{68    const int va[4] = { 1, 4, 6, 9 };69    const int vb[3] = { 2, 3, 7 };70    struct node *a = from_array(va, 4);71    struct node *b = from_array(vb, 3);72    struct node *m = merge_lists(a, b);73    print_list(m);74    printf("%d comparisons\n", comparisons);75    free_list(m);76    return 0;77}

Taking the smaller front node

main keeps the keys in two arrays, va = 1, 4, 6, 9 and vb = 2, 3, 7, and from_array turns each into a list by pushing its keys from the last, so each list comes out in the array’s order. a is 1, 4, 6, 9 and b is 2, 3, 7, both sorted. The nodes sit on the heap in the order they were made: a’s from 9 down to 1, then b’s from 7 down to 2.

The merge is the same idea as merging two sorted arrays (5.5): look at the front of each list, take the smaller, and repeat. With arrays, each taken value is copied into a third array. With lists there is nothing to copy. The taken node is already on the heap; it only has to be linked after the last node taken. So merge_lists keeps a pointer, tail, on the last node of the merged list, and each step makes one write, tail->next = a or tail->next = b.

Watch the six comparisons in the clip:

After the sixth, b is empty. What is left of a, the 9 node, is already a sorted list, so line 62 attaches it with one write: 7’s next ← 0x1000. The merged chain runs 0x1060 → 0x10c0 → 0x10a0 → 0x1040 → 0x1020 → 0x1080 → 0x1000, which is 1, 2, 3, 4, 6, 7, 9. No node was made or copied; only arrows changed. Some next fields did not even change: 9’s was NULL before and after.

The code and its cost

The loop

struct node *merge_lists(struct node *a, struct node *b)
{
    struct node dummy;
    struct node *tail = &dummy;
    dummy.next = NULL;
    while (a != NULL && b != NULL) {
        comparisons++;
        if (a->key <= b->key) {
            tail->next = a;
            a = a->next;
        } else {
            tail->next = b;
            b = b->next;
        }
        tail = tail->next;
    }
    tail->next = (a != NULL) ? a : b;
    return dummy.next;
}

Inside the loop, a and b are the fronts of what is left of each list. The taken node is linked after tail, its list’s pointer moves on, and tail moves onto it. The loop stops when either list is empty, and line 62 attaches the other, whatever is left of it, in one write. comparisons is a counter at file scope, outside every frame, so the picture counts it beside the output.

The dummy node

The first node taken has no node before it: it is the merged list’s head. Without help, the first step would need its own if to set the head instead of writing a next field. The dummy node gives tail somewhere to start. dummy is an ordinary struct node, a local in merge_lists’s frame at 0x7f88, not on the heap; tail starts on it, the first write goes into dummy.next, and at the end dummy.next is the head of the merged list, which merge_lists returns. Its key is never written. In the picture dummy is one box with a question mark, and its next field is not drawn: while tail is on dummy, tail’s box shows 0x7f88, dummy’s own address.

Equal keys

The test is a->key <= b->key, so when the fronts are equal, a’s node is taken first. Equal keys come out in the order their lists had them, a’s before b’s. A merge with this property is called stable, and Merge sort (17.5) depends on it.

What it costs

Here m and n are the lengths of the two lists. Every comparison takes one node, and the loop stops when one list is empty, so at least one node is still waiting: at most m + n − 1 comparisons. Here, 4 + 3 − 1 = 6, the most there can be, because when b ran out only one node, 9, was left in a: the two largest keys, 7 and 9, were in different lists. Each node taken costs one write, and the leftover list one write in all. The merge makes no nodes and copies no keys: its extra memory is dummy and three pointers, whatever the lengths, O(1) in the notation of Time and space complexity (3.3). Merging arrays needs an output array as long as both.

Running it yourself

The code pane shows merge_lists and main. The full program, merge.c, starts with the list helpers from Removing from a linked list, then the counter and from_array. Build and run it with:

gcc -std=c11 -Wall -Wextra -pedantic merge.c -o merge
./merge

It prints 1 2 3 4 6 7 9 , then 6 comparisons.

Worked example

Merge 1 3 5 with 2 4 6. The fronts are compared five times: 1 and 2 (take 1), 3 and 2 (take 2), 3 and 4 (take 3), 5 and 4 (take 4), 5 and 6 (take 5). a is empty, and 6 is attached with one write. 5 comparisons for 6 nodes, the most possible.

Merge 1 2 3 with 7 8 9. 1 and 7, 2 and 7, 3 and 7: a is empty after 3 comparisons, and the whole of b, 7 8 9, goes on with the one write of line 62. A list that is entirely smaller costs one comparison per node in it, and nothing for the other.

Without the dummy. Take dummy out and tail has nowhere to start. The function would need, first, a check that neither list is empty, returning the other if one is; then an if to pick the smaller front as the head and point tail at it; and only then the loop. That is two extra cases before the loop. With dummy, the loop and line 62 cover both: an empty list stops the loop at once, and line 62 hands back the other list.

Two lists of 5. At most 5 + 5 − 1 = 9 comparisons. And if a is empty from the start, the loop never runs, line 50 sets dummy.next to NULL and line 62 sets it to b, and merge_lists returns b.

Where it’s used

Merge sort on lists. Merge sort splits a list in halves, sorts each and merges them; on linked lists the merge above needs no buffer at all, which is why it is the usual way to sort a linked list. Merge sort (17.5) builds it.

Sorted runs. Programs that sort more data than fits in memory sort it in pieces and then merge the sorted pieces.

Event lists. Two lists of events, each in time order, combine into one timeline with a merge.

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.