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.3 required=5.0 tests=BAYES_00,INVALID_MSGID autolearn=no autolearn_force=no version=3.4.4 X-Google-Language: ENGLISH,ASCII-7-bit X-Google-Thread: 10f6aa,e1e578817780dac2 X-Google-Attributes: gid10f6aa,public X-Google-Thread: 109fba,baaf5f793d03d420 X-Google-Attributes: gid109fba,public X-Google-Thread: fc89c,97188312486d4578 X-Google-Attributes: gidfc89c,public X-Google-Thread: 1014db,6154de2e240de72a X-Google-Attributes: gid1014db,public X-Google-Thread: 103376,97188312486d4578 X-Google-Attributes: gid103376,public From: ok@goanna.cs.rmit.edu.au (Richard A. O'Keefe) Subject: Re: Should I learn C or Pascal? Date: 1996/08/19 Message-ID: <4v99re$g3s@goanna.cs.rmit.edu.au>#1/1 X-Deja-AN: 175067444 references: <4u7hi6$s2b@nntp.seflin.lib.fl.us> <4uo74j$95p@ns.broadvision.com> <4uu9v3$hrp@goanna.cs.rmit.edu.au> <840279292snz@genesis.demon.co.uk> organization: Comp Sci, RMIT, Melbourne, Australia newsgroups: comp.lang.c,comp.lang.c++,comp.unix.programmer,comp.lang.ada,comp.os.msdos.programmer nntp-posting-user: ok Date: 1996-08-19T00:00:00+00:00 List-Id: I wrote: >>the modern heapsort has the virtue that its worst case is O(nlgn) which >>makes it a better bet for soft-real-time work. Lawrence Kirby writes: >Heapsort has always been O(n log n). You're right that a guaranteed >reasonable worst case is sometimes useful. Mea culpa. What I meant, of course, was that it has now been known for several years (from my known knowedge) [since 1968 at least, according to Robert Dewar] how to do heapsort with 1.0 N.lg N + cruft element comparisons. >>For general use, a well engineered merge sort is as good as a well engineered >>quicksort; sometimes better. >It is close but very rare indeed for a heapsort to run faster than >a quicksort. Perhaps, but I wrote "a well engineered MERGE sort" at this point, and that's what I meant. It is quite common for a well engineered merge sort to beat quick sort; I've beaten UNIX qsort by 20% on occasion. (It is *much* harder to beat the Bentley & someone "engineered" quick sort in Software Practice & Experience a year or two ago, but it isn't at all hard to *match* it). >As far as the C language is concerned merge sort and radix sort aren't good >choices for qsort(). That was not proposed by anyone. It is so ruddy obvious that a sorting interface which accepts an arbitrary comparison function cannot use radix sort that surely Kirby didn't need to mention it. As for whether merge sort is a good choice for qsort(): if you have the spare memory (which in most cases on workstations and mainframes you _have_) and if you care about performance (which again one usually does) merge sort makes an *excellent* implementation of qsort(), if you are as good a hacker as whoever would have written the quicksort. UNIX on a PDP-11 *had* to make use of a less efficient sort than merge sort because in 64k you didn't have the memory to spare for anything. -- Australian citizen since 14 August 1996. *Now* I can vote the xxxs out! Richard A. O'Keefe; http://www.cs.rmit.edu.au/~ok; RMIT Comp.Sci.