Merging 3 sorted linked lists 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-&gt;num : (c2) ? c2-&gt;num : (c3) ? c3-&gt;num : 0;
    if(c1 &amp;&amp; c1-&gt;num &lt;= n) {
        n = c1-&gt;num;
        i = 1;
    }
    if(c2 &amp;&amp; c2-&gt;num &lt;= n) {
        n = c2-&gt;num;
        i = 2;
    }
    if(c3 &amp;&amp; c3-&gt;num &lt;= n) {
        n = c3-&gt;num;
        i = 3;
    }
    switch(i) {
    case 1:
        curr = c1;
        c1 = c1-&gt;next;
        break;
    case 2:
        curr = c2;
        c2 = c2-&gt;next;
        break;
    case 3:
        curr = c3;
        c3 = c3-&gt;next;
        break;
    default :
        curr = NULL;
    }
    if (!ret) ret = curr;
    else last-&gt;next = curr;
    last = curr;
}
return ret;
}
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 &amp;&amp; (!c2 || (c2 &amp;&amp; c3-&gt;num &lt; c2-&gt;num))) {
            clist *temp = c2;
            c2 = c3;
            c3 = temp;
        }
        if (c2 &amp;&amp; (!c1 || (c1 &amp;&amp; c2-&gt;num &lt; c1-&gt;num))) {
            clist *temp = c1;
            c1 = c2;
            c2 = temp;
        }
        // use c1 as next node
        if (curr) {
            curr-&gt;next = c1;
            curr = curr-&gt;next;
        } else {
            ret = curr = c1;
        }
        if (c1) {
            c1 = c1-&gt;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 &lt;stdio.h&gt;
#include &lt;stdarg.h&gt;
#include &lt;stdlib.h&gt;
#include &lt;string.h&gt;
#include &lt;assert.h&gt;
#include &lt;stdbool.h&gt;
#include &lt;time.h&gt;
#include &lt;math.h&gt;

/* 
 * 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-&gt;num = n;
        n += increment;
        curr-&gt;next = NULL;
        if (last == NULL) {
            first = last = curr;
        } else {
            last-&gt;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-&gt;num;
    for (list = list-&gt;next; list; list = list-&gt;next) {
        if (prev &gt; list-&gt;num) {
            return false;
        }
        prev = list-&gt;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 &gt; 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