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 <stdio.h>#include <stdlib.h>typedef struct List {    int val;    struct List *next;} List; List *new(int value){    List *list = malloc(sizeof(List));    list->next = NULL;    list->val = value;    return list;}void freeList(List *list){    List *node = list;    while(node != NULL) {        List *n = node->next;        free(node);        node = n;    } }void print(List *list){    for(List *node = list; node != NULL; node = node->next) {        printf(%d , node->val);            }    printf(\n);}List *merge(List *part1, List *part2, int (*cmp)(const void *, const void *)){    List *temp;    if(cmp(&part1->val, &part2->val) < 0) {        temp = part1;        part1 = part1->next;        }       else {        temp = part2;        part2 = part2->next;    }    List *current = temp;    while(part1 != NULL && part2 != NULL) {        if(cmp(&part1->val, &part2->val) < 0) {            current->next = part1;            part1 = part1->next;        }        else {            current->next = part2;            part2 = part2->next;        }        current = current->next;    }    while(part1 != NULL) {        current->next = part1;        current = current->next;        part1 = part1->next;    }    while(part2 != NULL) {        current->next = part2;        current = current->next;        part2 = part2->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->next) {            if(i == mid) {                midNode = node;            }             i++;        }        List *midNodeNext = midNode->next;        List *part1 = mergeSort(start, midNode, startIndex, mid, cmp);        List *part2 = mergeSort(midNodeNext, stop, mid + 1, stopIndex, cmp);        return merge(part1, part2, cmp);    }    start->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->next) {        if(node->next == NULL) {            last = node;        }    }    last->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;}
Sort a linked list with merge sort in C
c;sorting;linked list;mergesort
Merging tails effectively wastes cycles. The nodes are already linked correctly.    if (part1 != NULL) {        current->next = part1;    }    if (part2 != NULL) {        current->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(&part1->val, &part2->val) < 0)makes your sort unstable. A correct comparison is either one of    if(cmp(&part2->val, &part1->val) > 0)    if(cmp(&part1->val, &part2->val) <= 0)Less indentation is easier to follow. I recommend to invert a recursion termination condition:    if (start == stop) {        start->next = NULL;        return start;    }    ...Avoid naked loops. The    for(List *node = start; node != stop; node = node->next) {        if(i == mid) {            midNode = node;        }        i++;    }should be factored out into a function    List * advance(List * start, int steps);