#include <stdio.h>
#include <stdlib.h>
#include <string.h>
 
/* #define DEBUG */
#if defined(DEBUG)
#include "xmalloc.h"
#else
#define xmalloc(x, y) malloc(x)
#define xfree(x, y) free(x)
#define xrealloc(x, y, z) realloc(x, y)
#define xmallocdump()
#endif
#define ID_GETLINE 1001
#define ID_BUFF    1002

#define BUFFSIZE 1024 /* >= 2 */
char *mygetline(FILE *fp) {
  static char inbuff[BUFFSIZE];
  char *outbuff_malloc, *tmpbuff;
  char *p, *r;
  int fEOL;
 
  if ((outbuff_malloc = xmalloc(1, ID_GETLINE)) == NULL) {
    return NULL;
  }
  *outbuff_malloc = '\0';
  fEOL = 0;
  do {
    r = fgets(inbuff, BUFFSIZE, fp);
    if (r == NULL)
      break;
    for (p = inbuff; *p != '\0'; p++)
      ;
    if (*(p - 1) == '\n')
      fEOL = 1;
    if ((tmpbuff = xrealloc(outbuff_malloc, strlen(outbuff_malloc) + strlen(inbuff) + 1, ID_GETLINE)) == NULL) {
      xfree(outbuff_malloc, ID_GETLINE);
      return NULL;
    }
    strcat(tmpbuff, inbuff);
    outbuff_malloc = tmpbuff;
  } while (!fEOL);
  if (strlen(outbuff_malloc) > 0) {
    for (p = outbuff_malloc; *p != '\0'; p++)
      ;
    if (*(p - 1) == '\n')
      *(p - 1) = '\0';
    return outbuff_malloc;
  }
  xfree(outbuff_malloc, ID_GETLINE);
  return NULL;
}

void Qsort(void *base, int n, int size, int (*cmp)(const void *, const void *)) {
  int min, max;
  void *tmp, *idx;
  if (n <= 1)
    return;
  if ((idx = malloc(size)) == NULL)
    return;
  if ((tmp = malloc(size)) == NULL) {
    free(idx);
    return;
  }
  memcpy(idx, base, size);
  min = 1;
  max = n - 1;
  while (min <= max) {
    if ((*cmp)(idx, base + min * size) < 0) {
      memcpy(tmp, base + min * size, size);
      memcpy(base + min * size, base + max * size, size);
      memcpy(base + max * size, tmp, size);
      max--;
    } else {
      memcpy(base + (min - 1) * size, base + min * size, size);
      min++;
    }
  }
  memcpy(base + max * size, idx, size);
  if (min > 1) {
    Qsort(base, min - 1, size, (int (*)(const void *, const void *))cmp);
  }
  if (max < n - 1) {
    Qsort(base + (max + 1) * size, n - 1 - max, size, (int (*)(const void *, const void *))cmp);
  }  
  free(tmp);
  free(idx);
}

int cmp_ascent(char **p, char **q) {
  return strcmp(*p, *q);
}

int cmp_descent(char **p, char **q) {
  return -strcmp(*p, *q);
}
 
int main(int argc, char *argv[]) {
  char **buff, **tmp, *p;
  int (*cmp)(char **, char **);
  int n, i;

  if (argc != 2) {
label_usage:
    fprintf(stderr, "usage: %s <option>\n", argv[0]);
    fprintf(stderr, "option: -a: ascent, -d: descent, input/output: stdio\n");
    return 1;
  }
  if (*argv[1] == '-' && *(argv[1] + 1) == 'a')
    cmp = cmp_ascent;
  else if (*argv[1] == '-' && *(argv[1] + 1) == 'd')
    cmp = cmp_descent;
  else
    goto label_usage;
  
#define C 3
  i = 0;
  n = C;
  if ((buff = xmalloc(C * sizeof(char *), ID_BUFF)) == 0) {
    fprintf(stderr, "memory full, aborted.\n");
    exit(1);
  }
#undef C
  while ((p = mygetline(stdin)) != 0) {
    if (!(i < n)) {
      n *= 2;
      if ((tmp = xrealloc(buff, n * sizeof(char *), ID_BUFF)) == 0) {
        fprintf(stderr, "memory full, aborted.\n");
        exit(1);
      }
      buff = tmp;
    }
    buff[i++] = p;
  }
  n = i;
  Qsort(buff, n, sizeof(char *), (int (*)(const void *, const void *))cmp);
  for (i = 0; i < n; i++) {
    printf("%s\n", buff[i]);
    xfree(buff[i], ID_GETLINE);
  }
  xfree(buff, ID_BUFF);
  xmallocdump();
  return 0;
}
/* end */

usage: /t <option>
option: -a: ascent, -d: descent, input/output: stdio