//==================================================== file = sortint.c =====
//=  Program to sort a series X integer values                              =
//=   - Use approximately O(n) Counting Sort if memory is available         =
//===========================================================================
//=  Notes:                                                                 =
//=    1) Input from input file "in.dat" to stdin (see example below)       =
//=        - No comments allowed                                            =
//=    2) Output is to stdout                                               =
//=    3) Useing Counting Sort if memory is available. Memory size is       =
//=       max value minus min value in series. If memory is not available   =
//=       then uses qsort.                                                  =
//=-------------------------------------------------------------------------=
//= Example "in.dat" file:                                                  =
//=                                                                         =
//=  10                                                                     =
//=  3                                                                      =
//=  6                                                                      =
//=  4                                                                      =
//=  1                                                                      =
//=  2                                                                      =
//=  2                                                                      =
//=  7                                                                      =
//=  6                                                                      =
//=-------------------------------------------------------------------------=
//= Example output (for above "in.dat")                                     =
//=                                                                         =
//=  1                                                                      =
//=  2                                                                      =
//=  2                                                                      =
//=  3                                                                      =
//=  4                                                                      =
//=  6                                                                      =
//=  6                                                                      =
//=  7                                                                      =
//=  10                                                                     =
//=-------------------------------------------------------------------------=
//=  Build: gcc sortint.c, bcc32 sortint.c, cl sortint.c                    =
//=-------------------------------------------------------------------------=
//=  Execute: sortint < in.dat                                              =
//=-------------------------------------------------------------------------=
//=  Author: Ken Christensen                                                =
//=          University of South Florida                                    =
//=          WWW: http://www.csee.usf.edu/~christen                         =
//=          Email: christen@csee.usf.edu                                   =
//=-------------------------------------------------------------------------=
//=  History: KJC (03/15/12) - Genesis                                      =
//=           KJC (05/23/18) - Minor clean up                               =
//===========================================================================
//----- Include files -------------------------------------------------------
#include <stdio.h>                 // Needed for printf() and feof()
#include <stdlib.h>                // Needed for exit() and atoi()

//----- Constants -----------------------------------------------------------
#define  M_SIZE    1048576         // Memory block for input

//----- Function prototypes -------------------------------------------------
int  comp(const void *p, const void *q);    // Compare p and q for qsort()

//===========================================================================
//=  Main program                                                           =
//===========================================================================
int main(void)
{
  int          *X;                 // Integer data from input file
  int          *Y;                 // Temporary storage for indexes
  int          N;                  // Number of values in "in.dat"
  int          min, max;           // Minimum and maximum values in X
  int          span;               // Span from max to min plus one
  int          i, j;               // Loop counters
  char         inputString[32];    // Input string
  int          input;              // Input value

  // Read integer input into block of size M_SIZE
  N = 0;
  X = (int *) malloc(M_SIZE*sizeof(int));
  while(1)
  {
    scanf("%s", inputString);
    input = atoi(inputString);
    if (feof(stdin)) break;
    N++;
    if ((N % M_SIZE) == 0)
      X = (int *) realloc(X, (N + M_SIZE)*sizeof(int));
    if (X == NULL)
    {
      fprintf(stderr,"*** ERROR 001 -- realloc() failed with N = %d", N);
      exit(-1);
    }
    X[N-1] = input;
  }
  X = (int *) realloc(X, N*sizeof(int));
  if (X == NULL)
  {
    fprintf(stderr,"*** ERROR 002 -- realloc() failed with N = %d", N);
    exit(-1);
  }

  // Sort the series X of size N using Counting Sort if sufficient memory
  min = max = X[0];
  for (i=1; i<N; i++)
    if (X[i] < min)
      min = X[i];
    else
      if (X[i] > max) max = X[i];
  span = max - min + 1;
  Y = (int *) calloc(sizeof(int), span);
  if (Y != NULL)
  {
    for (i=0; i<N; i++)
      Y[X[i] - min]++;
    j = 0;
    for (i=0; i<span; i++)
      while(Y[i]--)
        X[j++] = i + min;
    free(Y);
  }
  else
  {
    fprintf(stderr, "WARNING 001 -- calloc() failed - reverting to qsort \n");
    qsort(X, N, sizeof(int), comp);
  }

  // Output the sorted series to stdout
  for (i=0; i<N; i++)
    printf("%d\n", X[i]);

  // Free X and return
  free(X);
  return 0;
}

//===========================================================================
//=  Function to compare two aruguments in an array of int                  =
//=   - Needed by qsort()                                                   =
//===========================================================================
int  comp(const void *p, const void *q)
{
  int *ptr1 = (int *)(p);
  int *ptr2 = (int *)(q);

  if (*ptr1 < *ptr2)
    return -1;
  else
    if (*ptr1 == *ptr2)
      return 0;
    else return 1;
}