Q:

Insert an unordered linked-list into an ordered linked-list

I recently have been given a challenge to write (an) efficient, elegant C function(s) which insert(s) the contents of an unordered linked-list into an ordered linked-list.
This is what I came up with:
node * insert(node * dest, node * src)
{
    node * current = dest;
    node * previous = NULL;

    //Deal with zero-length destination list
    if (dest == NULL) { return src; }

    //Deal with putting it at the start
    if (src->data >= dest->data)
    {
        src->next = dest;
        return src;
    }

    //Iterate to find the right position
    while (current->data <= src->data)
    {
        previous = current;
        current = current->next;
    }
    previous->next = src;
    src->next = current;
    return dest;
}

node * insertLL(node * sorted, node * unsorted)
{
    while(unsorted != NULL)
    {
        node * next_unsorted = unsorted->next;
        sorted = insert(sorted, unsorted);
        unsorted = next_unsorted;
    }

    return sorted;
}

Can you all critique my functions - especially whether or not my insert() function is efficient?  It seems rather large to me.

A:

It appears to me that your algorithm simply inserts each of the unsorted elements into the sorted list one at a time.  If you had m unsorted and n sorted, this would basically give you an operation count proportional to m * n.
If you were to create an array of the unsorted items and then sort them (m log m operations), you could then use a merge (m + n operations) to construct a new list.
To be brutally honest, the differences wouldn't necessarily become apparent until m and/or n started getting large but it's something to keep in mind.

As an aside, I think you may also run into problems where the unsorted item belongs at the end of the sorted list. You have special handling for the start but if you're inserting 7 into the list {1,2,3}, you'll end up trying to dereference NULL because current has run off the end of the sorted list (current->data <= src->data will be true for all non-NULL values of current).

