/* prog8.7.c */
#include <stdio.h>
#include <stdlib.h>

#define less(A, B) ((A) < (B))

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

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

link merge(link a, link b)
  { struct node head; link c = &head;
    while ((a != NULL) && (b != NULL))
      if (less(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 mergesort(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(mergesort(a), mergesort(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 = mergesort(a->next);

  printf("Lista ordenada:\n");
  print_list(a->next);
  return 0;
}