/* msort.c (emx+gcc) */

/* This sample program shows how to use a simple variant of merge sort
   to sort the lines of a file. */

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

#define FALSE 0
#define TRUE  1

static int comparisons;

struct list_el
{
  struct list_el *next;
  char *string;
};


static int compare (const struct list_el *p1, const struct list_el *p2)
{
  ++comparisons;
  return strcmp (p1->string, p2->string);
}


static void mergesort (struct list_el **head)
{
  struct list_el *s1, *s2, *t1, *t2, **a1, **a2;
  struct list_el *temp;
  int run_length, n1, n2, flag, cmp;

  /* Split the list into two lists, s1 and s2.  The lengths of s1 and
     s2 differ at most by 1. */

  s1 = s2 = NULL;
  a1 = &s1; a2 = &s2;
  for (t1 = *head;;)
    {
      if (t1 == NULL)
        break;
      temp = t1->next; t1->next = NULL;
      *a1 = t1; a1 = &t1->next;
      t1 = temp;

      if (t1 == NULL)
        break;
      temp = t1->next; t1->next = NULL;
      *a2 = t1; a2 = &t1->next;
      t1 = temp;
    }
  run_length = 1;

  /* Repeat merging and splitting the lists until one of them is
     empty. */

  while (s1 != NULL && s2 != NULL)
    {
      /* Merge the lists s1 and s2 containing runs of length
         RUN_LENGTH and split the result into lists t1 and t2
         containing runs of length 2*RUN_LENGTH. */

      t1 = NULL; t2 = NULL;
      a1 = &t1; a2 = &t2;
      flag = 0;

      while (s1 != NULL || s2 != NULL)
        {
          /* Merge and split one run. */
          n1 = n2 = run_length;
          for (;;)
            {
              if (n1 == 0 || s1 == NULL)
                {
                  if (n2 == 0 || s2 == NULL)
                    break;
                  cmp = 1;
                }
              else if (n2 == 0 || s2 == NULL)
                cmp = -1;
              else
                cmp = compare (s1, s2);

              /* Select the smaller element of the two. */

              if (cmp <= 0)
                {
                  temp = s1; s1 = s1->next; --n1;
                }
              else
                {
                  temp = s2; s2 = s2->next; --n2;
                }

              /* Add the element two t1 or t2 (split). */

              temp->next = NULL;
              if (flag == 0)
                {
                  *a1 = temp; a1 = &temp->next;
                }
              else
                {
                  *a2 = temp; a2 = &temp->next;
                }

            }
          flag = !flag;
        }

      /* Use t1 and t2 as new s1 and s2, respectively. */

      s1 = t1; s2 = t2;
      run_length *= 2;
    }

  /* Return the non-empty list, which contains one run and therefore
     is sorted. */

  *head = (s1 != NULL ? s1 : s2);
}


static void usage (void)
{
  fputs ("Usage: msort [-c] [-v] [<input_file>]\n", stderr);
  exit (1);
}


int main (int argc, char *argv[])
{
  char buffer[512], *p;
  char check, verbose;
  struct list_el *head, **add, *pel;
  FILE *f;
  int i, n;

  check = verbose = FALSE;
  for (i = 1; i < argc; ++i)
    {
      if (argv[i][0] != '-')
        break;
      if (strcmp (argv[i]+1, "c") == 0)
        check = TRUE;
      else if (strcmp (argv[i]+1, "v") == 0)
        verbose = TRUE;
      else
        usage ();
    }
  if (i == argc)
    f = stdin;
  else if (i+1 == argc)
    {
      f = fopen (argv[i], "rt");
      if (f == NULL)
        {
          fputs ("Cannot open input file\n", stderr);
          return 1;
        }
    }
  else
    usage();
  head = NULL; add = &head; n = 0;
  while (!feof (f))
    {
      if (fgets (buffer, sizeof (buffer), f) == NULL)
        break;
      p = strchr (buffer, '\n');
      if (p != NULL) *p = 0;
      pel = malloc (sizeof (*pel));
      p = strdup (buffer);
      if (pel == NULL || p == NULL)
        {
          fputs ("Out of memory\n", stderr);
          return 2;
        }
      pel->string = p;
      pel->next = NULL;
      *add = pel; add = &pel->next;
      ++n;
    }
  if (ferror (f))
    {
      fputs ("Error reading input file\n", stderr);
      return 2;
    }
  if (verbose)
    fprintf (stderr, "%d line%s read\n", n, (n == 1 ? "" : "s"));
  comparisons = 0;
  mergesort (&head);
  for (pel = head; pel != NULL; pel = pel->next)
    if (puts (pel->string) == EOF)
      {
        fputs ("Error writing output file\n", stderr);
        return 2;
      }
  if (check)
    {
      i = 0;
      for (pel = head; pel != NULL; pel = pel->next)
        {
          ++i;
          if (pel->next != NULL && strcmp (pel->string, pel->next->string) > 0)
            fprintf (stderr, "Internal error, i=%d\n", i);
        }
      if (i != n)
        fprintf (stderr, "Internal error, i=%d, n=%d\n", i, n);
    }
  if (verbose)
    fprintf (stderr, "%d comparison%s\n", comparisons,
             (comparisons == 1 ? "" : "s"));
  return 0;
}
