/*
A much faster sorting program.

Try creating a rand.out file with 10000 random numbers.
Do this as a programmer, not a user:
first write a rand program that reads n
and does printf("%d\n",rand()) n times,
using the standard library function rand();
then type
   rand > rand.out
   10000
to create the rand.out file.

Now feed rand.out to dyn6 and dyn7, and see how long they take:
   time dyn6 < rand.out > dyn6.out
   time dyn7 < rand.out > dyn7.out
Compare the output files to make sure dyn6 and dyn7 did the same job:
   cmp dyn6.out dyn7.out
If the output files are identical, cmp won't print anything.
Finally, remove the random files:
   rm rand.out dyn6.out dyn7.out

The sorting algorithm in dyn7.c is called ``heapsort.''
It's explained in subsequent MCS courses.
*/

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

int doublearray_append(double **a,int *aspace,int *alen,double d)
{
  if (*alen == *aspace) {
    int yspace = *aspace * 2 + 1;
    double *y = (double *) realloc(*a,yspace * sizeof(double));
    if (!y) return 0;
    *a = y;
    *aspace = yspace;
  }
  (*a)[*alen] = d;
  ++*alen;
  return 1;
}

/* sort a[0], a[1], ..., a[n-1] */
void sort(double *a,int n)
{
  double t;
  int i = n;
  int p;
  int q;

  --a; /* now want to sort a[1], a[2], ..., a[n] */

  while (n > 1) {
    if (i > 1) t = a[--i];
    else { t = a[n]; a[n--] = a[1]; }

    q = i;
    while ((p = q * 2) < n) {
      if (a[p + 1] >= a[p]) ++p;
      a[q] = a[p]; q = p;
    }
    if (p == n) {
      a[q] = a[p]; q = p;
    }
    while ((q > i) && (t > a[p = q / 2])) {
      a[q] = a[p]; q = p;
    }
    a[q] = t;
  }
}

int main(void)
{
  double *x = 0;
  int xspace = 0;
  int xlen = 0;
  double d;
  int i;

  while (scanf("%lf",&d) == 1)
    if (!doublearray_append(&x,&xspace,&xlen,d)) {
      printf("out of memory\n");
      exit(1);
    }

  sort(x,xlen);
  for (i = 0;i < xlen;++i) printf("%f\n",x[i]);

  return 0;
}