[comp.lang.c] Re: Sorting Algorithm

[Chris Torek]

Archive-name: torek-lsort/25-Aug-90
Original-posting-by: chris at mimsy.umd.edu (Chris Torek)
Original-subject: Re: Sorting Algorithm
Reposted-by: emv at math.lsa.umich.edu (Edward Vielmetti)

[Reposted from comp.lang.c.
Comments on this service to emv at math.lsa.umich.edu (Edward Vielmetti).]

Just for fun, here is yet another linked list sort.  This attempts to
use the fewest instructions possible for those n-squared loops :-)

#include <stddef.h>

/*
 * Sort a linked list in which the `next' pointer is the first entry.
 * A pointer to the (new) list head is returned.
 *
 * lsort() performs a binary merge sort.  The length parameter is
 * optional; if 0, lsort runs a first pass over the list to find the
 * length.
 */
struct list {			/* pseudo */
	struct list *next;
};

void *
lsort(list, listlen, compare)
	void *list;
	int listlen;
	register int (*compare)();
{
	struct list *hd;
	register struct list *p, **xp, *a, *b;
	register int i, left, mergelen;
	register struct list **ea, **eb;

	hd = list;
	if (listlen == 0) {
		for (i = 0, p = hd; p; p = p->next)
			i++;
		listlen = i;
	}

	/* if list is empty, this loop does not run */
	for (mergelen = 1; mergelen < listlen; mergelen <<= 1) {
		/*
		 * Merge ceil(listlen/mergelen) lists, pairwise.
		 *
		 * On each trip through the loop below, we split the
		 * list headed by p into two sublists a and b of length
		 * mergelen or less, followed by a trailing part p.
		 * List a will always be complete, but list b may be
		 * short when we near the tail.  (It can even be empty;
		 * we handle this as a special case for speed reasons.)
		 * We then merge lists a and b, sticking each next
		 * element at *xp and tracking xp along.  Eventually
		 * either a or b runs out; we can then tack on what
		 * remains of the other.
		 */
		left = listlen;
		p = hd;
		xp = &hd;
		do {
			/*
			 * Make list a, length mergelen, and figure
			 * out how many are left after that.  If none
			 * or negative, list b will be empty; stop.
			 */
			i = mergelen;
			if ((left -= i) <= 0) {
				*xp = p;
				break;
			}
			for (a = p; --i > 0; p = p->next)
				/* void */;
			ea = &p->next, p = p->next, *ea = NULL;

			/* make list b, length min(mergelen,left) */
			i = mergelen;
			if ((left -= i) < 0)
				i += left;
			for (b = p; --i > 0; p = p->next)
				/* void */;
			eb = &p->next, p = p->next, *eb = NULL;

			/* tail in p, empty iff left<=0 */
			for (;;) {
				/* append from appropriate sublist */
				if ((*compare)((void *)a, (void *)b) <= 0) {
					*xp = a;
					xp = &a->next;
					if ((a = a->next) == NULL) {
						*xp = b;
						xp = eb;
						break;
					}
				} else {
					*xp = b;
					xp = &b->next;
					if ((b = b->next) == NULL) {
						*xp = a;
						xp = ea;
						break;
					}
				}
			}
		} while (left > 0);
	}
	return ((void *)hd);
}
-- 
In-Real-Life: Chris Torek, Univ of MD Comp Sci Dept (+1 301 405 2750)
Domain:	chris at cs.umd.edu	Path:	uunet!mimsy!chris