/*------------------------------------------------------------------*/
/* sortdmmll.c (A Linked List)                                      */
/*------------------------------------------------------------------*/

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

struct Node
{
   double dItem;
   struct Node *psNextNode;
};

/*------------------------------------------------------------------*/

struct Node *newNode(double dItem, struct Node *psNextNode)

/* Return a new node whose fields are dItem and psNextNode. */

{
   struct Node *psNewNode;
   psNewNode = (struct Node*)malloc(sizeof(*psNewNode));
   assert(psNewNode != NULL);
   psNewNode->dItem = dItem;
   psNewNode->psNextNode = psNextNode;
   return psNewNode;
}

/*------------------------------------------------------------------*/

struct Node *merge(struct Node *psHead1, struct Node *psHead2)
{
   struct Node *psHead3;

   if (psHead1 == NULL) return psHead2;
   if (psHead2 == NULL) return psHead1;
   if (psHead1->dItem < psHead2->dItem)
   {
      psHead3 = psHead1;
      psHead3->psNextNode = merge(psHead1->psNextNode, psHead2);
   }
   else
   {
      psHead3 = psHead2;
      psHead3->psNextNode = merge(psHead1, psHead2->psNextNode);
   }
   return psHead3;
}

/*------------------------------------------------------------------*/

struct Node *mergesort(struct Node *psHead)
{
   struct Node *psHead1;
   struct Node *psHead2;

   if ((psHead == NULL) || (psHead->psNextNode == NULL)) return psHead;

   psHead1 = psHead;
   psHead2 = psHead->psNextNode;
   while ((psHead2 != NULL) && (psHead2->psNextNode != NULL))
   {
      psHead = psHead->psNextNode;
      psHead2 = psHead->psNextNode->psNextNode;
   }
   psHead2 = psHead->psNextNode;
   psHead->psNextNode = NULL;

   return merge(mergesort(psHead1), mergesort(psHead2));
}

/*------------------------------------------------------------------*/

int main(int argc, char *argv[])

/* Read numbers from stdin, and write them in ascending order to 
   stdout. */

{
   struct Node *psHead;
   struct Node *psCurrentNode;
   struct Node *psNextNode;
   double dNumber;

   /* Read the numbers into a linked list. */

   psHead = NULL;
   while (scanf("%lf", &dNumber) != EOF)
      psHead = newNode(dNumber, psHead);

   /* Sort the linked list. */

   psHead = mergesort(psHead);

   /* Write the numbers from the linked list. */

   for (psCurrentNode = psHead;
        psCurrentNode != NULL;
        psCurrentNode = psCurrentNode->psNextNode)
      printf("%g\n", psCurrentNode->dItem);

   /* Free the linked list. */

   for (psCurrentNode = psHead;
        psCurrentNode != NULL;
        psCurrentNode = psNextNode)
   {
      psNextNode = psCurrentNode->psNextNode;
      free(psCurrentNode);
   }

   return 0;
}