From mboxrd@z Thu Jan 1 00:00:00 1970 X-Spam-Checker-Version: SpamAssassin 3.4.4 (2020-01-24) on polar.synack.me X-Spam-Level: X-Spam-Status: No, score=-1.9 required=5.0 tests=BAYES_00 autolearn=ham autolearn_force=no version=3.4.4 X-Google-Language: ENGLISH,ASCII-7-bit X-Google-Thread: 103376,385be4c68a9e4de6 X-Google-Attributes: gid103376,public X-Google-ArrivalTime: 2002-07-06 06:40:23 PST Path: archiver1.google.com!postnews1.google.com!not-for-mail From: dewar@gnat.com (Robert Dewar) Newsgroups: comp.lang.ada Subject: Re: Smart sorting algorithm ? Date: 6 Jul 2002 06:40:22 -0700 Organization: http://groups.google.com/ Message-ID: <5ee5b646.0207060540.62f0fef4@posting.google.com> References: <3D21D581.6EF6CB06@despammed.com> <3D220691.26F596F2@despammed.com> NNTP-Posting-Host: 205.232.38.243 Content-Type: text/plain; charset=ISO-8859-1 Content-Transfer-Encoding: 8bit X-Trace: posting.google.com 1025962823 32408 127.0.0.1 (6 Jul 2002 13:40:23 GMT) X-Complaints-To: groups-abuse@google.com NNTP-Posting-Date: 6 Jul 2002 13:40:23 GMT Xref: archiver1.google.com comp.lang.ada:26901 Date: 2002-07-06T13:40:23+00:00 List-Id: "Tarjei T. Jensen" wrote in message news:... > Wes Groleau wrote: > > > have a look into D.E.Knuth: The Art of Computer Programming, Vol > > > 3: Sorting and Searching. Subsection 5.3.1: Minimum Comparison > > > Sorting. > > > > Thanks, I will do that if I can find it. > > (I got volume one at a garage sale, and > > I've never seen any of the others anywhere.) > > Knuth is an excellent example of a bit twiddler in action. As far as I'm > concerned the point gets lost in a sea of details written in mix. Not at all. I suspect you have not really made an effort to read these books carefully. The point of the MIX sections (which are a very small fraction of the material) is to try to analyze *actual* performance of algorithms as opposed to theoretical O(f(n)) behavior. It's an interesting attempt, not made by any other algorithm book author, and indeed not always successful since it involves going to a very low level, but it is not clear that there is any way of doing this that would be more successful. In fact all algorithms in Knuth are stated in a very readable pseudo-language and if you do not care for the detailed performance analysis in the MIX code sections, just skip them, but don't throw out the baby with the bath water, and don't use the MIX sections as an excuse not to thoroughly read the material in the first three Knuth volumes (and if you have the math, follow through the mathematical reasoning carefully).