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
#include

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) next;
}
else {
temp = part2;
part2 = part2->next;
}

List *current = temp;

while(part1 != NULL && part2 != NULL) {
if(cmp(&part1->val, &part2->val) 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) {

-
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);

StackExchange Code Review Q#85186, answer score: 2