Sort a linked list with merge sort in C

Question

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

• Loki Astari: new() is not a great name for a function. Maybe newNode()

Answer 1

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