linked list

mergesortlinkedlist.c

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

#define DEBUG 1

typedef struct CELL *LIST;

struct CELL {
  int element;
  LIST next;
};

// create a new list cell
LIST create_list(int value) {
  LIST list = (LIST)malloc(sizeof(struct CELL));
  list->element = value;
  list->next = NULL;
  return list;
}

// insert a cell after another cell
LIST insert_after(LIST dest, LIST src) {
  if (dest != NULL) dest->next = src;
  return src;
}

void insert_after_list(LIST *head, LIST *tail, LIST src) {
  *tail = insert_after(*tail, src);
  if (*head == NULL) *head = *tail;
}

void insert_after_and_advance(LIST *head, LIST *tail, LIST *runner) {
  insert_after_list(head, tail, *runner);
  *runner = (*runner)->next;
}

void free_list(LIST list) {
  while (list != NULL) {
    LIST next = list->next;
    free(list);
    list = next;
  }
}

void show_list(LIST list) {
  LIST cell;
  for (cell = list; cell != NULL; cell = cell->next) {
    printf("%s%d", cell == list ? "" : ", ", cell->element);
  }
  puts("");
}

// merge sorted list a and sorted list b.
// returns the resulting list
LIST merge(LIST a, LIST b) {
  LIST head = NULL, tail = NULL;

#if DEBUG
  puts("==============================merge");
  printf("a : "); show_list(a);
  printf("b : "); show_list(b);
#endif
  
  for (;;) {
    if (a != NULL && b != NULL) {
      insert_after_and_advance(&head, &tail, a->element <= b->element ? &a : &b);
    } else if (a != NULL) {
      insert_after_and_advance(&head, &tail, &a);
    } else if (b != NULL) {
      insert_after_and_advance(&head, &tail, &b);
    } else {
      break;
    }
  }

#if DEBUG
  printf("result : "); show_list(head);
#endif

  return head;
}

// merge sort a list.
// returns the resulting list.
LIST merge_sort(LIST list) {
  LIST mid = NULL;
  LIST tail;
  int size = 1; /* for non-NULL list, the size is at least 1. */

  /* base case: empty list can't be sorted */
  if (list == NULL) return NULL;

  /* base case: list with single element does not need to be sorted */
  if (list->next == NULL) return list;

  for (tail = list; tail != NULL; tail = tail->next) {
    size++;
    if (size % 2 == 0) mid = mid == NULL ? list : mid->next;
  }

  /* break the list into two lists: list and tail */
  tail = mid->next;
  mid->next = NULL;

  /* recursion */
  list = merge_sort(list);
  tail = merge_sort(tail);

  /* merging */
  return merge(list, tail);
}

int main(int argc, char **argv) {
  int i;
  LIST head = NULL, tail = NULL;
  srand(time(NULL));
  for (i = 0; i < 100; i ++) {
    insert_after_list(&head, &tail, create_list(rand() % 100));
  }
  puts("before sorting ->");
  show_list(head);
  head = merge_sort(head);
  puts("after sorting ->");
  show_list(head);
  free_list(head);
  return 0;
}