/*
 * This code is from "Algorithms in C, Third Edition,"
 * by Robert Sedgewick, Addison Wesley Longman, 1998.
 * (possibly with some small changes---check the book!)
 */
#include <stdio.h>
#include <stdlib.h>

typedef struct node* link;
struct node { int item; link next; };

void print_list(link t)
{
  for ( ; t; t = t->next) 
    printf("%d\n", t->item);
}

link merge(link a, link b)
  { struct node head; link c = &head;
    while ((a != NULL) && (b != NULL))
      if (a->item < b->item)
        { c->next = a; c = a; a = a->next; }
      else
        { c->next = b; c = b; b = b->next; }
    c->next = (a == NULL) ? b : a;
    return head.next;
  }

link lmergesort(link c)
  { link a, b;
    if (c->next == NULL) return c;
    a = c; b = c->next;
    while ((b != NULL) && (b->next != NULL))
      { c = c->next; b = b->next->next; }
    b = c->next; c->next = NULL;
    return merge(lmergesort(a), lmergesort(b));
  }

int main(int argc, char *argv[])
{
  int i, N = atoi(argv[1]);
  struct node heada;
  link t, a = &heada;
  
  for (i = 0, t = a; i < N; i++) {
      t->next = malloc(sizeof *t); 
      t = t->next; t->next = NULL;
      t->item = rand() % 1000; 
    }
  printf("Lista original:\n");
  print_list(a->next);
  a->next = lmergesort(a->next);
  printf("Lista ordenada:\n");
  print_list(a->next);
  return 0;
}