/*
 *   A quicksort routine; nothing special.  Only works on machines
 *   which store the most significant byte of a longword in the
 *   first byte, and so on.
 */
#include "stdio.h"
char **lineptrs ;
long numlines ;
long lineptrsize ;
char inbuf[255] ;
char **ssmin[25], **ssmax[25] ;
int stval ;
void *lmalloc() ;
#define MEMCHUNK 4096
#define swap(a, b) {t= a;a= b;b= t;}
char *tbuf ;
int bytesleft ;
int reverse ;
char *saveit(s)
register char *s ;
{
   int len = (strlen(s) + (2*sizeof(long)-1)) & ~(sizeof(long)-1) ;
   register char *p ;

   if (len > bytesleft) {
      tbuf = (char *)lmalloc((long)MEMCHUNK) ;
      if (tbuf == NULL)
         error("! couldn't allocate memory") ;
      bytesleft = MEMCHUNK ;
   }
   p = tbuf ;
   while (*p++ = *s++) ;
   s = tbuf ;
   tbuf += len ;
   while (p < tbuf)
      *p++ = 0 ;
   bytesleft -= len ;
   return(s) ;
}
long strlcmp(a, b)
register long *a, *b ;
{
   while (*a == *b && *a) {
      a++ ;
      b++ ;
   }
   return(*b - *a) ;
}
error(s)
char *s ;
{
   fputs("sort: ", stdout) ;
   puts(s) ;
   if (*s == '!')
      exit(1) ;
}
getlines() {
   register int c ;
   register char *p ;
   register long i ;
   char **olineptrs ;

   lineptrsize = 0 ;
   numlines = 0 ;
   while (1) {
      p = inbuf ;
      while ((c=getchar())!=EOF && c != 10) {
         *p++ = c ;
         if (p > inbuf + 250)
            error("! input line too long") ;
      }
      *p = 0 ;
      if (c==EOF && p==inbuf)
         break ;
      p = saveit(inbuf) ;
      if (numlines >= lineptrsize) {
         olineptrs = lineptrs ;
         lineptrsize = lineptrsize + (MEMCHUNK/sizeof(char *)) ;
         lineptrs = (char **)lmalloc((long)sizeof(char *)*lineptrsize) ;
         if (lineptrs == NULL)
            error("! couldn't allocate memory") ;
         for (i=0; i<lineptrsize-MEMCHUNK/sizeof(char *); i++)
            lineptrs[i] = olineptrs[i] ;
         free(olineptrs) ;
      }
      lineptrs[numlines++] = p ;
   }
}
sortlines() {
   register char **i, **j ;
   register char *medp ;
   char **min, **max, **med ;
   register char *t ;

   stval = 0 ;
   min = lineptrs ;
   max = lineptrs + numlines - 1 ;
   while (1) {
      if (max < min + 3) {
         if (max > min) {
            if (strlcmp(*max, *min)<0)
               swap(*max, *min) ;
            if (max == min + 2) {
               if (strlcmp(*(min+1), *min)<0)
                  swap(*(min+1),*min) ;
               if (strlcmp(*max, *(min+1))<0)
                  swap(*max,*(min+1)) ;
            }
         }
         if (stval > 0) {
            stval-- ;
            min = ssmin[stval] ;
            max = ssmax[stval] ;
         } else
            break ;
      } else {
         med = min + (max - min) / 2 ;
         if (strlcmp(*max, *min)<0)
            swap(*max, *min) ;
         if (strlcmp(*med, *min)<0)
            swap(*med, *min) ;
         if (strlcmp(*max, *med)<0)
            swap(*max, *med) ;
         i = min + 1 ;
         j = max - 1 ;
         medp = *med ;
         while (1) {
            if (strlcmp(medp, *i)>=0) {
               i++ ;
               if (i>j)
                  break ;
            } else
               goto checkj ;
            if (strlcmp(*j, medp)>=0) {
               j-- ;
               if (i>j)
                  break ;
            } else
               goto checki ;
            continue ;
checki:
            while (strlcmp(medp, *i)>=0 && i<=j)
               i++ ;
            goto over ;
checkj:
            while (strlcmp(*j, medp)>=0 && i<=j)
               j-- ;
over:
            if (i < j) {
               swap(*i, *j)
               i++ ;
               j-- ;
               if (i>j)
                  break ;
            } else
               break ;
         }
         if (j-min > max-i) {
            ssmin[stval] = min ;
            ssmax[stval] = j ;
            stval++ ;
            min = i ;
         } else {
            ssmin[stval] = i ;
            ssmax[stval] = max ;
            stval++ ;
            max = j ;
         }
      }
   }
}
putlines() {
   register long i ;

   if (reverse)
      for (i=0; i<numlines; i++)
         puts(lineptrs[i]) ;
   else
      for (i=numlines-1; i>=0; i--)
         puts(lineptrs[i]) ;
}
main(argc, argv)
int argc ;
char *argv[] ;
{
   while (argc > 1 && argv[1][0]=='-') {
      argc-- ;
      argv++ ;
      switch(argv[0][1]) {
case 'r' : reverse = 1 ;
        break ;
default :  break ;
      }
   }
   if (argc > 1) {
      argc-- ;
      argv++ ;
      if (freopen(argv[0], "r", stdin) == NULL)
         error("! couldn't open input file") ;
   }
   if (argc > 1) {
      argc-- ;
      argv++ ;
      if (freopen(argv[0], "w", stdout) == NULL)
         error("! couldn't open output file") ;
   }
   getlines() ;
   if (numlines > 1)
      sortlines() ;
   putlines() ;
   fclose(stdout) ;
}
_wb_parse() {}