Sort a linked list with merge sort in C This is my version of a linked list in C. The function mergeSort requires a reference to the first and to the last nodes, as well as the indices of the first and the last node and a comparator.

You need to compile this source code using C99 standard in order to get it working.

#include &lt;stdio.h&gt;
#include &lt;stdlib.h&gt;

typedef struct List {
    int val;
    struct List *next;
} List; 

List *new(int value)
{
    List *list = malloc(sizeof(List));
    list-&gt;next = NULL;
    list-&gt;val = value;

    return list;
}

void freeList(List *list)
{
    List *node = list;
    while(node != NULL) {
        List *n = node-&gt;next;
        free(node);
        node = n;
    } 
}

void print(List *list)
{
    for(List *node = list; node != NULL; node = node-&gt;next) {
        printf("%d ", node-&gt;val);        
    }
    printf("\n");
}

List *merge(List *part1, List *part2, int (*cmp)(const void *, const void *))
{
    List *temp;

    if(cmp(&amp;part1-&gt;val, &amp;part2-&gt;val) &lt; 0) {
        temp = part1;
        part1 = part1-&gt;next;    
    }   
    else {
        temp = part2;
        part2 = part2-&gt;next;
    }

    List *current = temp;

    while(part1 != NULL &amp;&amp; part2 != NULL) {
        if(cmp(&amp;part1-&gt;val, &amp;part2-&gt;val) &lt; 0) {
            current-&gt;next = part1;
            part1 = part1-&gt;next;
        }
        else {
            current-&gt;next = part2;
            part2 = part2-&gt;next;
        }
        current = current-&gt;next;
    }

    while(part1 != NULL) {
        current-&gt;next = part1;
        current = current-&gt;next;
        part1 = part1-&gt;next;
    }

    while(part2 != NULL) {
        current-&gt;next = part2;
        current = current-&gt;next;
        part2 = part2-&gt;next;
    }

    return temp;
}

List *mergeSort(List *start,
                List *stop,
                int startIndex,
                int stopIndex,
                int (*cmp)(const void *, const void *))
{
    if(start != stop) {
        int mid = (startIndex + stopIndex) / 2;
        int i = startIndex;

        List *midNode = NULL;
        for(List *node = start; node != stop; node = node-&gt;next) {
            if(i == mid) {
                midNode = node;
            } 
            i++;
        }
        List *midNodeNext = midNode-&gt;next;

        List *part1 = mergeSort(start, midNode, startIndex, mid, cmp);
        List *part2 = mergeSort(midNodeNext, stop, mid + 1, stopIndex, cmp);

        return merge(part1, part2, cmp);
    }

    start-&gt;next = NULL;
    return start;
}

int cmp(const void *a, const void *b)
{
    return *(int *)a - *(int *)b;
}

List *push(List *list, List *node) 
{
    List *last;
    for(List *node = list; node != NULL; node = node-&gt;next) {
        if(node-&gt;next == NULL) {
            last = node;
        }
    }
    last-&gt;next = node;

    return node;
}

int main()
{
    List *list = new(9);

    push(list, new(4));
    push(list, new(3));
    push(list, new(2));
    push(list, new(1));
    List *stop = push(list, new(8));

    list = mergeSort(list, stop, 0, 5, cmp);

    print(list);

    freeList(list);

    return 0;

}
Merging tails effectively wastes cycles. The nodes are already linked correctly.

    if (part1 != NULL) {
        current-&gt;next = part1;
    }

    if (part2 != NULL) {
        current-&gt;next = part2;
    }


is enough.
A single most important feature of merge sort is stability: elements compared equal remain in the original order. A comparison

    if(cmp(&amp;part1-&gt;val, &amp;part2-&gt;val) &lt; 0)


makes your sort unstable. A correct comparison is either one of

    if(cmp(&amp;part2-&gt;val, &amp;part1-&gt;val) &gt; 0)
    if(cmp(&amp;part1-&gt;val, &amp;part2-&gt;val) &lt;= 0)

Less indentation is easier to follow. I recommend to invert a recursion termination condition:

    if (start == stop) {
        start-&gt;next = NULL;
        return start;
    }
    ...

Avoid naked loops. The

    for(List *node = start; node != stop; node = node-&gt;next) {
        if(i == mid) {
            midNode = node;
        }
        i++;
    }


should be factored out into a function

    List * advance(List * start, int steps);