Merging 3 sorted linked lists

Question

I already know how to merge two linked list, but I needed to code a function that'll merge three already sorted linked lists into one.

I wrote a code and it is working fine, it takes care of null lists and so. I just don't know if it's efficient enough. What do you think? How can I improve this code?

typedef struct clist {
int num;
struct clist *next;
} clist;

clist *cmerge(clist *c1, clist *c2, clist *c3) {
// Input parameters are pointers to the first items of the lists, out parameter is the pointer to the first item of the merged list
clist *ret = NULL, *curr = NULL, *last = NULL;
int i=1,n;
while(i) {
    i = 0;
    n = (c1) ? c1->num : (c2) ? c2->num : (c3) ? c3->num : 0;
    if(c1 && c1->num <= n) {
        n = c1->num;
        i = 1;
    }
    if(c2 && c2->num <= n) {
        n = c2->num;
        i = 2;
    }
    if(c3 && c3->num <= n) {
        n = c3->num;
        i = 3;
    }
    switch(i) {
    case 1:
        curr = c1;
        c1 = c1->next;
        break;
    case 2:
        curr = c2;
        c2 = c2->next;
        break;
    case 3:
        curr = c3;
        c3 = c3->next;
        break;
    default :
        curr = NULL;
    }
    if (!ret) ret = curr;
    else last->next = curr;
    last = curr;
}
return ret;
}

Answer 1

The code works as it is, but it uses a number of local variables that aren't actually needed. An alternative approach might be this:

clist *cmerge(clist *c1, clist *c2, clist *c3) {
    clist *ret;
    clist *curr = NULL;
    while (1) {
        if (c3 && (!c2 || (c2 && c3->num < c2->num))) {
            clist *temp = c2;
            c2 = c3;
            c3 = temp;
        }
        if (c2 && (!c1 || (c1 && c2->num < c1->num))) {
            clist *temp = c1;
            c1 = c2;
            c2 = temp;
        }
        // use c1 as next node
        if (curr) {
            curr->next = c1;
            curr = curr->next;
        } else {
            ret = curr = c1;
        }
        if (c1) {
            c1 = c1->next;
        } else {
            return ret;
        }
    }
    return ret;   // never actually reached
}

The code works by arranging the three lists so that the smallest next number is always pointed to by c1. That simplifies appending the node to the result list.

Another approach is to use the two-list merge twice. That approach has the advantage that it could easily be adapted to be a variadic function taking any number of lists at a slight cost in efficiency.

Performance Testing

Results of time testing on two Linux boxes are shown below, demonstrating that this code runs measurably faster than the original.

First, here's the test harness code:

#include <stdio.h>
#include <stdarg.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>
#include <stdbool.h>
#include <time.h>
#include <math.h>

/* 
 * the various implementations go here
 */

/* start at some number in (0,100) and increment by
 * some other number in (0,10) for count iterations
 * passed pointer is assumed to have count contiguous
 * nodes.
 */
clist *fill_random_list(int count, clist *curr) {
    clist *first = NULL, *last = NULL;
    assert(curr != NULL);
    int increment = rand() % 10;
    for (int n=rand() % 100 ; count; --count, ++curr) {
        curr->num = n;
        n += increment;
        curr->next = NULL;
        if (last == NULL) {
            first = last = curr;
        } else {
            last->next = curr;
            last = curr;
        }
    }
    return first;
}

// return true iff list is sorted
bool is_sorted(clist *list) 
{
    if (list == NULL) {
        return true;
    }
    int prev = list->num;
    for (list = list->next; list; list = list->next) {
        if (prev > list->num) {
            return false;
        }
        prev = list->num;
    }
    return true;
}

int main()
{
    const size_t list_size = 5000000;
    srand(time(NULL));
    clist *one = malloc(list_size * sizeof(clist));
    clist *two = malloc(list_size * sizeof(clist));
    clist *three = malloc(list_size * sizeof(clist));
    clist *big;
    struct {
        const char *name;
        clist* (*func)(clist*, clist*, clist*);
        double elapsed;
    } tests[] = {
        { "original", cmerge_orig, 0 },
        { "Edward", cmerge_edward, 0 },
        { "mdfst13", cmerge_mdfst13, 0 },
        { NULL, NULL, 0}
    };

    for (int iterations = 100; iterations; --iterations) {
        for (size_t i=0; tests[i].func; ++i) {
            fill_random_list(list_size, one);
            assert(is_sorted(one));
            fill_random_list(list_size, two);
            assert(is_sorted(two));
            fill_random_list(list_size, three);
            assert(is_sorted(three));
            clock_t start = clock();
            big = tests[i].func(one, two, three);
            tests[i].elapsed += (double)(clock() - start)/CLOCKS_PER_SEC;
            assert(is_sorted(big));
        }
    }
    // print results
    for (size_t i = 0; tests[i].func; ++i) {
        printf("%12s\t%.10f\t%f%% %s than %s\n", tests[i].name, tests[i].elapsed,
            100.0*fabs(tests[i].elapsed-tests[0].elapsed)/tests[0].elapsed, 
            (tests[i].elapsed > tests[0].elapsed ? "slower" : "faster"),
            tests[0].name
        );
    }
    free(one);
    free(two);
    free(three);
}

The code creates three sorted lists with random-ish values. It uses assert() to rather gracelessly bail out on error (either a supposedly sorted list isn't or out of memory) and the timing doesn't account for possible rollover, but it works well enough for this purpose.

Merging 3 lists, each 5,000,000 items, cumulative time for 100 iterations

x86_64, 8 core, 3.4GHz, gcc 5.3.1

    original    2.3338780000    0.000000% faster than original
      Edward    2.2184270000    4.946745% faster than original
     mdfst13    4.1236940000    76.688499% slower than original

ARM v7, 4 core, 900MHz, gcc 4.6.3

    original    57.1399730000   0.000000% faster than original
      Edward    53.4537210000   6.451267% faster than original
     mdfst13    63.4887120000   11.110854% slower than original

Compile command:

gcc -O2 -Wall -Wextra -pedantic -std=c99 mergetest.c -o mergetest

Answer 2

I already know how to merge two linked list, but I needed to code a function that'll merge three already sorted linked lists into one.

If I saw this as a requirement and had a function (say the one from this post)

static clist * cmerge2(clist *c1, clist *c2) {
    clist dummy_head = { 0, NULL };
    clist *tail = &dummy_head;

    while ( c1 && c2 ) {   
        clist **min = (c1->num <= c2->num) ? &c1 : &c2;
        clist *next = (*min)->next;
        tail = tail->next = *min;
        *min = next;
    }

    tail->next = c1 ? c1 : c2;

    return dummy_head.next;
}

that would merge two lists into one, I'd just do

clist *cmerge(clist *c1, clist *c2, clist *c3) {
    return cmerge2(cmerge2(c1, c2), c3);
}

Unless performance is at an absolute premium, this is going to be good enough. And I'm not sure that it's necessarily worse. Note that your code has to check a number of edge cases on every iteration even though they only change status once. You also have to do three comparisons for every node. This code only does one comparison per node (although it does does process c1 and c2 twice, so two comparisons for their nodes). The simpler code might actually do fewer tests, as it has to check fewer situations. You should time it on some standard inputs to see.

This code is much shorter and easier to maintain. It's also better tested, as there are many existing tests for merging two lists.

Answer 3

For concise code you'd better to use min priority queue. Note that specific implementation of priority queue for three items is rather simple (for example, binary heap based on array containing three pairs (L=list number; V=current value (num field) of this list)
Pseudocode:

Add elements with the first values of all lists to PQ
At each stage extract from PQ item with minimal V
Add this value to the new list
Insert into PQ item with the same L and with next value
(If next field of current list is nil (end), add pair with MaxInt value)
If PQ.ExtractMin returns MaxInt - stop the process, all lists are exhausted