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: Joe Keane Subject: Re: Should I learn C or Pascal? Date: 1996/08/23 Message-ID: <4vk6b1$el3@shellx.best.com>#1/1 X-Deja-AN: 175963643 sender: jgk@best.com references: <4u7hi6$s2b@nntp.seflin.lib.fl.us> <4uu9v3$hrp@goanna.cs.rmit.edu.au> <840279292snz@genesis.demon.co.uk> <4v99re$g3s@goanna.cs.rmit.edu.au> summary: Merge sort is good. organization: none keywords: qsort newsgroups: comp.lang.c,comp.lang.c++,comp.unix.programmer,comp.lang.ada,comp.os.msdos.programmer Date: 1996-08-23T00:00:00+00:00 List-Id: In article <4v99re$g3s@goanna.cs.rmit.edu.au> Richard A. O'Keefe writes: >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. These days, with virtual memory, asking for a bit of extra space is probably a good idea if it gives you a faster algorithm. I'd say that once you have the `qsort' interface, calling a function for comparison, quicksort has lost its biggest advantage, the tight inner loops. Indeed the GNU `qsort' is actually a merge sort, pretty much textbook, and it beats any quick sort i've seen. The FreeBSD `mergesort' function is considerably more funky, but it seems to work very well. More specifically, what the GNU `qsort' function does is this: if the extra space needed is small, allocate it off the stack, otherwise call malloc, and if that fails, fall back on a quicksort. It's attention to detail like this that distinguishes robust library functions from some code that someone was playing around with. -- Joe Keane, amateur mathematician