/* find -nx pattern */
#include<stdio.h>
#include<string.h>
#include<stdlib.h>

#define  MAXLINES  5000
#define  MAXLEN    1000
#define  ALLOCSIZE 10000

static char allocbuf[ALLOCSIZE];
static char *allocp = allocbuf;
char *lineptr[MAXLINES];
char *alloc(int n);
int readlines(char *lineptr[], int nlines);
void writelines(char *lineptr[], int nlines);
void qsort1(void *lineptr[], int left, int right, int (*comp) (void *, void *));
int numcmp(char *, char *);
int getline(char *line, int max);
void swap1(void *v[], int i, int j);

int main(int argc, char *argv[])
{
 int nlines;
 int numeric = 0;

 if (argc > 1 && strcmp(argv[1], "-n") == 0) numeric=1;
 if ((nlines = readlines(lineptr, MAXLINES)) >= 0)
  {
     qsort1((void**) lineptr, 0, nlines-1, (int (*)(void*,void*))(numeric ? numcmp : strcmp));
     writelines(lineptr, nlines);
     return 0;
  }
 else
 {
   printf("Input too big to sort\n");
   return 1;
 }
}

void qsort1(void *v[], int left, int right, int (*comp) (void *, void *))
 {
   int i, last;


   if (left >= right) return;
   swap1(v, left, (left+right)/2);
   last = left;

   for (i=left+1; i<=right; i++)
    if ((*comp)(v[i], v[left]) < 0) swap1(v, ++last, i);
   swap1(v, left, last);
   qsort1(v, left, last-1, comp);
   qsort1(v, last+1, right, comp);
 }


int numcmp(char *s1, char *s2)
 {
   double v1, v2;
   v1 = atof(s1);
   v2 = atof(s2);

   if (v1 < v2) return -1;
   else if (v1 > v2) return 1;
   else
     return 0;
 }


void swap1(void *v[], int i, int j)
 {
   char *temp;
   temp = v[i];
   v[i] = v[j];
   v[j] = temp;
 }

int readlines(char *lineptr[], int maxlines)
 {
   int len, nlines;
   char *p, line[MAXLEN];

   nlines = 0;

   while (( len = getline(line, MAXLEN)) > 0)
    if((nlines >= maxlines) || (p = alloc(len)) == NULL)
       return -1;
    else
      {
         line[len-1] = '\0';
         strcpy(p, line);
         lineptr[nlines++] = p;
      }
     return nlines;
}

void writelines(char *lineptr[], int nlines)
 {
   int i;

   for(i=0; i < nlines; i++)
    printf("%s\n", lineptr[i]);
 }




int getline(char *line, int max)
{
  int c, i=0;

  while(--max > 0 && (c=getchar()) != EOF && c!='\n')
    { *line++=c; i++; }
  if(c=='\n')
   { *line++=c; i++; }
  *line='\0';
 return i;
}

char *alloc(int n)
{
  if(allocbuf + ALLOCSIZE - allocp >= n)
   {
      allocp += n;
      return allocp -n;
   }
  else
   return 0;
}