List mergesort

lms.c

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

typedef struct list_node_s {
  struct list_node_s *next;
  int val;
} LIST_NODE;

LIST_NODE *sort(LIST_NODE *a) {
  if (!a || !a->next) return a;
  LIST_NODE *b, *t;
  for (t = a, b = a->next; b && b->next; t = t->next, b = b->next->next) ;
  b = t->next;
  t->next = NULL;
  a = sort(a);
  b = sort(b);
  LIST_NODE d[1] = {{NULL}};
  t = d;
  while (a && b) {
    if (a->val < b->val) {
      t->next = a;
      t = a;
      a = a->next;
    } else {
      t->next = b;
      t = b;
      b = b->next;
    }
  }
  t->next = a ? a : b;
  return d->next;
}

LIST_NODE *make_node(int val, LIST_NODE *next) {
  LIST_NODE *p = malloc(sizeof *p);
  p->val = val;
  p->next = next;
  return p;
}

int main(void) {
  LIST_NODE *list = NULL;
  for (int n = 0; n < 100; ++n) list = make_node(rand(), list);
  for (LIST_NODE *p = list; p; p = p->next) printf("%d\n", p->val);
  list = sort(list);
  printf("\n");
  for (LIST_NODE *p = list; p; p = p->next) printf("%d\n", p->val);
  return 0;
}


// Slight optimization to reduce comparisons. Verified clang makes better code.
LIST_NODE *sort2(LIST_NODE *a) {
  if (!a || !a->next) return a;
  LIST_NODE *b, *t;
  for (t = a, b = a->next; b && b->next; t = t->next, b = b->next->next) ;
  b = t->next;
  t->next = NULL;
  a = sort(a);
  b = sort(b);
  LIST_NODE d[1] = {{NULL}};
  t = d;
  if (!a) {
    t->next = b;
    return d->next;
  }
  if (!b) {
    t->next = a;
    return d->next;
  }
  for (;;) {
    if (a->val < b->val) {
      t->next = a;
      t = a;
      a = a->next;
      if (!a) {
        t->next = b;
        return d->next;
      }
    } else {
      t->next = b;
      t = b;
      b = b->next;
      if (!b) {
        t->next = a;
        return d->next;
      };
    }
  }
}