/*
 * This code is (basically) from "Algorithms in C, Third Edition,"
 * by Robert Sedgewick, Addison Wesley Longman, 1998.
 */

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

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

/* Prototipos das funcoes */

link merge(link a, link b);
link mergesort(link c);
void imprima_lista(link p);

/* Programa principal */

int main(int argc, char *argv[])
{
  int i, N=atoi(argv[1]);

  struct node heada;
  
  link t, a = &heada, b;
  
  for (i = 0, t = a; i < N; i++)
    {
      t->next = malloc(sizeof *t); 
      t = t->next; t->next = NULL;
      t->item = rand() % 1000; 
    }

  imprima_lista(a->next);
  
  b=mergesort(a);

  imprima_lista(b->next);

  return 0;
}

/* Implementacoes das funcoes */

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

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

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