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

#define MAX 1000

typedef struct _node {
   int key;             /* The key value to be stored in a node */
   struct _node *next;  /* Pointer to the next node */
} node;

typedef struct {
   unsigned int size;   /* Number of elements in the list */
   node *first;         /* Pointer to the first element in the list */
} list;

list initList ( unsigned int n )
{
   list L;
   node *p;
   int i;

   L.size = n;
   if (n == 0) L.first = NULL;
   else {
      p = L.first = (node *)malloc(sizeof(node));
      p -> key = 1 + rand() % MAX;
      for (i=1; i<n; ++i) {
         p -> next = (node *)malloc(sizeof(node));
         p = p -> next;
         p -> key = 1 + rand() % MAX;
      }
      p -> next = NULL;
   }
   return L;
}

void printList ( list L )
{
   unsigned int i;
   node *p;
   int ncp = 4;

   if (L.size > 0) {
      p = L.first;
      for (i=0; i<L.size; ++i) {
         printf("%4d", p -> key);
         p = p -> next;
         if (++ncp == 18) {
            printf("\n");
            ncp = 0;
         }
      }
   }
   if (ncp) printf("\n");
}

/* Merge two sorted lists into a single sorted list */
list merge ( list L1, list L2 )
{
}

/* The merge sort algorithm for linked lists */
list mergeSort ( list L )
{
   list L1, L2;

   /* Break the list in two parts: first to be headed by L1, second by L2 */

   /* Make recursive calls on the two sublists */

   /* Merge the two sorted sublists */

}

int main ()
{
   unsigned int n;
   list L;

   srand((unsigned int)time(NULL));
   printf("Enter size of list : "); scanf("%u", &n); printf("%u\n", n);
   L = initList(n);
   printf("Original list : "); printList(L);
   L = mergeSort(L);
   printf("Sorted list   : "); printList(L);
}