Doubly linked list - Update list->tail after a merge sort

Your algorithm uses O(N) stack space by recursing in the merge function for every step. With this method, it would be very cumbersome to keep track of the tail node. You can simply scan the list to find it and update the list structure in linklist_sort. This extra step does not change the complexity of the sorting operation. You can save some time by starting from the current value of link->tail: the loop will stop immediately if the list was already sorted.

Here is a modified version:

void linklist_sort(struct linklist *list, int (*comp)(const void *, const void *)) {
    list->head = merge_sort(list->head, comp);
    if (list->tail) {
        struct node *tail = list->tail;
        while (tail->next)
            tail = tail->next;
        list->tail = tail;
    }
}

Sorting linked lists with merge sort should only use O(log(N)) space and O(N log(N)) time.

Here are some ideas to improve this algorithm:

• since you know the length of the list, you don't need to scan the full list for splitting. You can just pass the lengths along with the list pointers and use that to determine where to split and only scan half the list.

• if you convert merge to a non-recursive version, you can keep track of the last node in the merge phase and update a pointer struct node **tailp passed as an argument to point to this last node. This would save the last scan, and removing the recursion will lower the space complexity. Whether this improves efficiency is not obvious, benchmarking will tell.

• from experience, sorting a linked list, singly and, a fortiori, doubly linked, is more efficiently implemented with an auxiliary array N pointers to the list nodes. You would sort this array and relink the nodes according to the order of the sorted array. The extra requirement is O(N) size.

Here is a modified version using the list lengths and with a non-recursive merge:

struct node {
    void *data;
    struct node *prev;
    struct node *next;
};

struct linklist {
    struct node *head;
    struct node *tail;
    size_t size;
};

static struct node *split(struct node *head, size_t pos) {
    struct node *slow = head;

    while (pos-- > 1) {
        slow = slow->next;
    }
    struct node *temp = slow->next;
    slow->next = NULL;
    return temp;
}

static struct node *merge(struct node *first, struct node *second,
                          int (*comp)(const void *, const void *))
{
    struct node *head = NULL;
    struct node *prev = NULL;
    struct node **linkp = &head;

    for (;;) {
        if (first == NULL) {
            second->prev = prev;
            *linkp = second;
            break;
        }
        if (second == NULL) {
            first->prev = prev;
            *linkp = first;
            break;
        }
        if (comp(first->data, second->data)) <= 0 {
            first->prev = prev;
            prev = *linkp = first;
            linkp = &first->next;
        } else {
            second->prev = prev;
            prev = *linkp = second;
            linkp = &second->next;
        }
    }
    return head;
}

static struct node *merge_sort(struct node *head, size_t size,
                               int (*comp)(const void *, const void *))
{
    if (size < 2) {
        return head;
    }

    struct node *second = split(head, size / 2);

    head = merge_sort(head, size / 2, comp);
    second = merge_sort(second, size - size / 2, comp);
    return merge(head, second, comp);
}

void linklist_sort(struct linklist *list, int (*comp)(const void *, const void *)) {
    list->head = merge_sort(list->head, comp, list->size);
    if (list->tail) {
        struct node *tail = list->tail;
        while (tail->next)
            tail = tail->next;
        list->tail = tail;
    }
}

Note that you could also simplify the merge function and not update the back pointers during the sort as you can relink the whole list during the last scan. This last scan would be longer and less cache friendly but it should still be more efficient and less error prone.

One option is to merge sort the nodes as if they were single list nodes, then make a one time pass when done to set the previous pointers, and update the tail pointer.

Another option would use something similar to C++ std::list and std::list::sort. A circular doubly linked list is used. There is one dummy node that uses "next" as "head" and "prev" as "tail". The parameters to merge sort and merge are iterators or pointers, and only used to keep track of run boundaries, as nodes are merged by moving them within the original list. The merge function merges nodes from a second run into the first run, using std::list::splice. The logic is if first run element is less than or equal to second run element, just advance the iterator or pointer to the first run, else remove the node from the second run and insert it before the current node in the first run. This will automatically update the head and tail pointers in the dummy node if involved in a remove + insert step.

Changing struct node to :

struct node
{
    struct node *next;           // used as head for dummy node
    struct node *prev;           // used as tail for dummy node
    void *data;
};

would be a bit more generic.

Since the dummy node is allocated when a list is created, then begin == dummy->next, last == dummy-> prev, and end == dummy.

I'm not the best person to provide deep analysis concerning algorithms Big-O notation. Anyways, answering to a question with an already accepted "canonic" answer is great, because there's the possibility to explore alternative solutions without too much pressure.
This it interesting even if, as you will see, the analysed solution is not better than the current solution presented in the question.

The strategy starts by wondering if it is possible keeping track of the candidate tail element without turning the code upside down. The main candidate is the function deciding the order of the nodes in the sorted list: the merge() function.

Now, since after the comparison we decide which node will come first in the sorted list, we will have a "loser" that will be nearer to the tail. So, with a further comparison with the current tail element for each step, in the end we will be able to update the tail element with the "loser of the losers".

The merge function will have the additional struct node **tail parameter (the double pointer is required because we will change the list tail field in place:

static struct node *merge(struct node *first, struct node *second, struct node **tail, int (*comp)(const void *, const void *))
{
    if (first == NULL)
    {
        return second;
    }
    if (second == NULL)
    {
        return first;
    }
    if (comp(first->data, second->data) < 0)
    {
        first->next = merge(first->next, second, tail, comp);

        /* The 'second' node is the "loser". Let's compare current 'tail' 
           with it, and in case it loses again, let's update  'tail'.      */
        if( comp(second->data, (*tail)->data) > 0)
            *tail = second;
        /******************************************************************/

        first->next->prev = first;
        first->prev = NULL;
        return first;
    }
    else
    {
        second->next = merge(first, second->next, tail, comp);

        /* The 'first' node is the "loser". Let's compare current 'tail' 
           with it, and in case it loses again, let's update  'tail'.      */
        if( comp(first->data, (*tail)->data) > 0)
            *tail = first;
        /******************************************************************/

        second->next->prev = second;
        second->prev = NULL;
        return second;
    }
}

There are no more changes required to the code, except those for the "propagation" of the tail double pointer parameter through merge_sort() and linklist_sort() functions:

static struct node *merge_sort(struct node *head, struct node **tail, int (*comp)(const void *, const void *));

void linklist_sort(List_t *list, int (*comp)(const void *, const void *))
{
    list->head = merge_sort(list->head, &(list->tail), comp);
}

The test

In order to test this modification I had to write a basic insert() function, a compare() function designed to obtain a sorted list in descending order, and a printList() utility. Then I wrote a main program to test all the stuff.

I did several tests; here I present just an example, in which I omit the functions presented in the question and above in this answer:

#include <stdio.h>

typedef struct node
{
    void *data;
    struct node *prev;
    struct node *next;
} Node_t;

typedef struct linklist
{
    struct node *head;
    struct node *tail;
    size_t size;
} List_t;

void insert(List_t *list, int data)
{
    Node_t * newnode = (Node_t *) malloc(sizeof(Node_t) );
    int * newdata = (int *) malloc(sizeof(int));
    *newdata = data;

    newnode->data = newdata;
    newnode->prev = list->tail;
    newnode->next = NULL;
    if(list->tail)
        list->tail->next = newnode;

    list->tail = newnode;

    if( list->size++ == 0 )
        list->head = newnode;   
}

int compare(const void *left, const void *right)
{
    if(!left && !right)
        return 0;

    if(!left && right)
        return 1;
    if(left && !right)
        return -1;

    int lInt = (int)*((int *)left), rInt = (int)*((int *)right);

    return (rInt-lInt); 
}

void printList( List_t *l)
{
    for(Node_t *n = l->head; n != NULL; n = n->next )
    {
        printf( " %d ->", *((int*)n->data));
    }
    printf( " NULL (tail=%d)\n", *((int*)l->tail->data));
}


int main(void)
{
  List_t l = { 0 };

  insert( &l, 5 );
  insert( &l, 3 );
  insert( &l, 15 );
  insert( &l, 11 );
  insert( &l, 2 );
  insert( &l, 66 );
  insert( &l, 77 );
  insert( &l, 4 );
  insert( &l, 13 );
  insert( &l, 9 );
  insert( &l, 23 );

  printList( &l );

  linklist_sort( &l, compare );

  printList( &l );

  /* Free-list utilities omitted */

  return 0;
}

In this specific test I got the following output:

 5 -> 3 -> 15 -> 11 -> 2 -> 66 -> 77 -> 4 -> 13 -> 9 -> 23 -> NULL (tail=23)
 77 -> 66 -> 23 -> 15 -> 13 -> 11 -> 9 -> 5 -> 4 -> 3 -> 2 -> NULL (tail=2)

Conclusions

• The good news is that theoretically speaking we still have an algorithm that, in the worst case, will have O(N log(N)) time complexity.
• The bad news is that, to avoid a linear search in a linked list (N "simple steps"), we have to do N*logN comparisons, involving a call to a function. This makes the linear search still a better option.