chris@mimsy.umd.edu (Chris Torek) (08/26/90)
Archive-name: torek-lsort/25-Aug-90
Original-posting-by: chris@mimsy.umd.edu (Chris Torek)
Original-subject: Re: Sorting Algorithm
Reposted-by: emv@math.lsa.umich.edu (Edward Vielmetti)
[Reposted from comp.lang.c.
Comments on this service to emv@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@cs.umd.edu Path: uunet!mimsy!chris