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->num : (c2) ? c2->num : (c3) ? c3->num : 0;
    if(c1 && c1->num num;
        i = 1;
    }
    if(c2 && c2->num num;
        i = 2;
    }
    if(c3 && c3->num 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;
}

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 num))) {
            clist *temp = c2;
            c2 = c3;
            c3 = temp;
        }
        if (c2 && (!c1 || (c1 && c2->num 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 
#include 
#include 
#include 
#include 
#include 
#include 
#include 

/* 
 * 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

StackExchange Code Review Q#129798, answer score: 6