/* $Id: sort.c,v 1.3 1998/10/17 13:24:50 fraserm Exp $
   $Log: sort.c,v $
   Revision 1.3  1998/10/17 13:24:50  fraserm
   ANSI-fied the code
   added "-" option to allow futrther options from standard input

   Revision 1.2  1996/09/12 14:20:56  fraser
   add module version printing

 * Revision 1.1  1996/09/12  13:20:09  fraser
 * Initial revision
 *
*/
/* sort.c: dictionary sorting function for agm
*/

char sort_RCSid[] = "$Revision: 1.3 $";

#include "agm.h"

void merge_sort (struct wnode **start, int length)
{
  struct wnode *p, *q, *s1, *s2;
  int i, cmp;

  if (length > 1) { /* split in half, sort each one, then merge results */
    for (p = *start, i = 1; p != NULL && i < length / 2; ++i, p = p->next);
    s1 = *start;
    s2 = p->next;
    p->next = NULL;
    merge_sort (&s1, i);
    merge_sort (&s2, length - i);
    p = *start = NULL;
    while (s1 != NULL && s2 != NULL) {
      if ((cmp = strcmp (s1->word, s2->word)) < 0) {
	q = s1->next;
	if (p == NULL) {
	  p = *start = s1;
	  p->next = NULL;
	}
	else {
	  p->next = s1;
	  p = s1;
	}
	s1 = q;
      }
      else { /* same, but other list */
	q = s2->next;
	if (p == NULL) {
	  p = *start = s2;
	  p->next = NULL;
	}
	else {
	  p->next = s2;
	  p = s2;
	}
	s2 = q;
	if (cmp == 0) { /* both words are equal, so we can dump the
			   other one */
	  s1 = s1->next;
	  ++dups_removed;
	}
      }
    }
    /* now add the remainder of whichever is left */
    if (s1 == NULL) { /* then s2 is left */
      p->next = s2;
    }
    else { /* s1 is left */
      p->next = s1;
    }
  }
}