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


| 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 Warnock			<>
627 26th Avenue			<URL:>
San Mateo, CA 94403		(650)572-2607