Merge sorting linked lists

Question

This works as expected and I want to get this code reviewed so that I can improve my coding ability.

I am concerned about readability and the quality of the code

#include<stdio.h>
#include<stdlib.h>


struct node
{   
    int element;
    struct node *next;
};



struct node* mergeList(struct node *list1, struct node *list2)
{
    struct node *root = NULL, *cur = NULL;

    if(list1 == NULL)
    {
        return list2;
    }

    if(list2 == NULL)
    {
        return list1;
    }   

    while( (list1 != NULL) && (list2 != NULL) )
    {
        struct node *tmp = malloc(sizeof(struct node));
        if( list1->element  < list2->element )
        {
            tmp->element = list1->element;
            tmp->next = NULL;
            list1 = list1->next;
        }
        else
        {
            tmp->element = list2->element;
            tmp->next = NULL;
            list2 = list2->next;

        }
        if(root == NULL)
        {
            root = tmp;
            cur = root;
        }
        else
        {
            cur->next = tmp;
            cur = tmp;
        }


    }


    while(list1 != NULL)
    {
        struct node *tmp = malloc(sizeof(struct node));
        tmp->element = list1->element;
        tmp->next = NULL;
        cur->next = tmp;
        cur = tmp;
        list1 = list1->next;
    }
    while(list2 != NULL)
    {
        struct node *tmp = malloc(sizeof(struct node));
        tmp->element = list2->element;
        tmp->next = NULL;
        cur->next = tmp;
        cur = tmp;
        list2 = list2->next;
    }


    return root;

}



void findMid(struct node *root, struct node **list1, struct node **list2)
{

    struct node *slow;
    struct node *fast;
    printf("\nIn Findmis\n");
    if( (root == NULL) || (root->next == NULL) )
    {
        *list1 = root;
        *list2 = NULL;
        return;
    }
    else
    {

        slow =  root;
        fast = root->next;
        while (fast != NULL) 
        {
            fast = fast->next;
            if(fast!=NULL)
            {
                slow = slow->next;
                fast = fast->next;
            }


        }


        *list1 = root;
        *list2 = slow->next;
        slow->next = NULL;

    }

}

void mergeSort(struct node **root)
{
    struct node *list1, *list2;
    struct node *head = *root;
    if( ( head  == NULL) || (head->next == NULL))
    {
        return;
    }


    findMid(head, &list1, &list2);

    if(list1 != NULL)
    printf("\nList1 = %d", list1->element);
    if(list2 != NULL)
    printf("\nList2 = %d", list2->element);
    mergeSort( &list1 );
    mergeSort( &list2 );

    *root = mergeList( list1, list2 ); 


}


void insertNodes(struct node **root, int key)
{
    struct node *tmp = malloc(sizeof(struct node));
    tmp->element = key;
    tmp->next = *root;
    *root = tmp;

}


void printList(struct node *root)
{
    while( root!= NULL)
    {
        printf("\n%d\n", root->element);
        root = root->next;
    }

}

int main(int argc, char *argv[])
{

    struct node *root1 = NULL;

    struct node *root2 = NULL;
    insertNodes( &root1, 1);
    insertNodes( &root1, 2);
    insertNodes( &root1, 3);
    insertNodes( &root1, 4);
    insertNodes( &root1, 5);
    printList(root1);
    mergeSort( &root1);
    printList(root1);
    return 0;

}

Answer 1

Preliminaries

Your compiler should have warned you that in main(), you never use list2. You do compile with warnings turned on, I hope?

Usually, the first node of a linked list is called the head. "Root" usually refers to the top of a tree.

mergeList() and findMid() are helper functions, which are designed to be used exclusively to support mergeSort(). It's a good habit to declare helper functions with the static modifier, so that they will be invisible to code in other .c files.

findMid()

The function could be better named, I think. "Find" sounds like a passive action, so you wouldn't expect that it might modify its inputs (which it does at the end: slow->next = NULL). I suggest calling it bisectList() instead.

Calling the function will always result in setting *list1 to root, so why bother making list1 an out-parameter? Going a step further, if there's only one output (list2), you can just return it normally.

So, the function could become static struct node *bisectList(struct node *head). Here's a more compact implementation.

/**
 * Returns a pointer to a node near the middle of the list,
 * after having truncated the original list before that point.
 */
static struct node *bisectList(struct node *head)
{
    /* The fast pointer moves twice as fast as the slow pointer. */
    /* The prev pointer points to the node preceding the slow pointer. */
    struct node *fast = head, *slow = head, *prev = NULL;

    while (fast != NULL && fast->next != NULL)
    {
        fast = fast->next->next;
        prev = slow;
        slow = slow->next;
    }

    if (prev != NULL)
    {
        prev->next = NULL;
    }
    return slow;
}

mergeList()

The function signature looks fine. There is altogether too much code, though.

One major problem, which @rolfl alluded to, is that you are duplicating every node that you encounter. Rather, you should be able to merge the lists just by manipulating the next pointers of the existing nodes.

To start with, you can eliminate the two special cases before the loop. (That meant, by the way, that your function not only leaked memory, it also had an inconsistent memory management policy: sometimes it would duplicate the list, and sometimes not.)

Once we have decided not to duplicate the nodes, the epilogue becomes trivial, and the last two loops can go away.

The code duplication within the main loop can be reduced by using a pointer to a pointer (which I call **min), referring to whichever list a head with the smaller value. The if (root == NULL) special case can be removed by initializing a pointer to a dummy head node.

static struct node* mergeList(struct node *list1, struct node *list2)
{
    struct node dummy_head = { 0, NULL }, *tail = &dummy_head;

    while ( (list1 != NULL) && (list2 != NULL) )
    {   
        struct node **min = (list1->element < list2->element) ? &list1 : &list2;
        struct node *next = (*min)->next;
        tail = tail->next = *min;
        *min = next;
    }
    tail->next = list1 ? list1 : list2;
    return dummy_head.next;
}

mergeSort()

It would be more natural to accept a struct node * and return a struct node *, I think.

You left in some printf() calls for debugging. Why not take advantage of the existing printList() function for that?

Most of the improvements are just natural consequences of the changes suggested above.

struct node *mergeSort(struct node *head) 
{   
    struct node *list1 = head; 
    if ( (list1 == NULL) || (list1->next == NULL) )
    {   
        return list1;
    }   

    struct node *list2 = bisectList(list1);

    printf("\nList1 = "); printList(list1);
    printf("\nList2 = "); printList(list2);

    return mergeList( mergeSort(list1), mergeSort(list2) );
}

Conclusion

Your understanding of the mergesort algorithm is generally sound. However, there were some massive memory leaks, and the implementation was verbose. Try to look for opportunities to design more natural function interfaces and reduce special cases.

Answer 2

I can't help but think that your solution suffers because of the malloc you do in the middle of the operation (mergeList), and the fact that your malloc's are never freed. You call the mergeList from the recursive part of your algorithm, so, in effect, you create \$log(n)\$ copies of unfreed memory each time you sort. (for 1024 members to be sorted, you will create an additional 10 copies of the data that you do not free)

Your leakage must be huge, and this is definitely bad practice.

I have not worked it out, yet, but I believe there must be a way to do the recursion in a way that does not require any copies/mallocs at all. The overall sort is an in-place sort, so there should be no need for the wastage.

Changing that in your algorithm would essentially be a rewrite though, and since this is such a large problem, there would be little value in small improvements in other places.

When returning up the stack in the recursion, consider returning the 'right' pointer to the next node in the list after the nodes that have just been merged. This will help you to do the merge sort without having to scan it first for a mid point too.