Subject: Re: Am I abusing SORT? It sure ain't working for me....
From: rpw3@rpw3.org (Rob Warnock)
Date: Sun, 26 Feb 2006 19:59:13 -0600
Newsgroups: comp.lang.lisp
Message-ID: <daCdncqdxvZswZ_ZnZ2dnUVZ_vidnZ2d@speakeasy.net>
rif  <rif@mit.edu> wrote:
+---------------
| I agree with Jens Axel Søgaard's first suggestion in
| that I believe what you want is a topological sort.
+---------------

Ditto.

+---------------
| The good news is it's O(n), not O(n log n). The bad news is that you
| probably get to right it yourself. The good news is it's not really hard.
+---------------

And the best news is that if you pick up your copy of Knuth TAoCP
Vol.1 Ch.2 "Data Structures" and look for "Algorithm T", you'll
find a nice reference implementation of topological sort.

Note: I've been using it on & off for *years*, coded up in whatever
language of the moment I was required to use. And then I don't use
it for a while, and the next time I need it I find that I've forgetten
the magic trick that makes it all "just work" and have to go back
to Knuth to learn the tricky bit again...  (*sigh*)


-Rob

-----
Rob Warnock			<rpw3@rpw3.org>
627 26th Avenue			<URL:http://rpw3.org/>
San Mateo, CA 94403		(650)572-2607