Path: utzoo!utgpu!news-server.csri.toronto.edu!rutgers!mit-eddie!bloom-beacon!eru!hagbard!sunic!enea!sommar
From: sommar@enea.se (Erland Sommarskog)
Newsgroups: comp.lang.misc
Subject: Re: A very brief history of optimal sorting methods
Message-ID: <2195@enea.se>
Date: 18 Nov 90 12:06:14 GMT
References: <5293:Nov1518:36:0490@kramden.acf.nyu.edu> <6067@lanl.gov> <1990Nov18.025739.2579@bushido.uucp>
Organization: Enea Data AB, Sweden
Lines: 33

Dave Caswell (dbc@bushido.uucp) writes:
>I read this group religiously and haven't seen Dan make statements that
>would backup the above claims.

The problem seems to be that he hasn't bothered to give any
technical arguments, but just tried to refute people with
statements like "Wrong." He may be right, but is he is certainly
not convincing. Disclaimer: due to mild interest and news
problems, I haven't read all articles on this thread.

>I often ask people about sorting at interviews, anyone
>who just regurgitates a quote like n log n loses.  I don't have a book
>that discusses sorting (Knuth etc.) that says the "answer" is n log n.

I guess you would never employ me. If we forget the recent
discussion I wouldn't have even the faintest idea. I recall
that I was exposed to exchange, bubble and quicksort in
school but whether they are linear, quadtratic or cubic
I don't bother about. (Don't we have rec.games.trivia for
that? :-) Seriously, the days are through when the most
essential in computer science and software engineering was
sorting algorithms. The day I need one, I will consult the
literature. Or simply think of the best way of calling
some built-in sort facility.

Oh, actually I wrote a generic Ada package for the topological
sorting algorithm presented in Knuth's book some years ago.
I seem to recall that this algorithm is linear in difference
to tsort(1) which is quadratic. (Topologcial sorting is a
special-purpose sorting and is not compatible normal sorting.)
-- 
Erland Sommarskog - ENEA Data, Stockholm - sommar@enea.se
"Handlar Hanssons halta h|na har haft hosta hela halva h|sten"