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=0.6 required=5.0 tests=BAYES_20,INVALID_MSGID autolearn=no autolearn_force=no version=3.4.4 X-Google-Language: ENGLISH,ASCII-7-bit 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: Blair Phillips Subject: Re: Teaching sorts [was Re: What's the best language to start with?] Date: 1996/08/15 Message-ID: <3212E94B.1233@spirit.net.au>#1/1 X-Deja-AN: 174324364 references: <31FBC584.4188@ivic.qc.ca> <01bb83f5$923391e0$87ee6fce@timpent.airshields.com> content-type: text/plain; charset=us-ascii organization: Spirit Networks - Canberra, Australia mime-version: 1.0 newsgroups: comp.lang.c,comp.lang.c++,comp.unix.programmer,comp.lang.ada x-mailer: Mozilla 3.0b6 (WinNT; I) Date: 1996-08-15T00:00:00+00:00 List-Id: Robert I. Eachus wrote: > > > Ah, the joys of being an old fart: > Yeah, anyone who didn't own 3 volumes of Knuth by 1974 loses! > > And for those of you who weren't around then, the reason for using > these sorts, and not quicksort was that you were really doing a > polyphase mergesort from tapes, and the inmemory sort of lots of > "little" files that could fit in memory was a first step. Among other > things, the elimination of the need for stack space--for quicksort-- > meant you could sort a slightly larger file. And that stack was > usually hand coded if you did use Quicksort... > The big win for polyphase sort came from the technique of inserting new items to replace those emitted from the heap. You end up with initial runs which average twice the size of your sorting space, a big win in those days when 4MB was a large memeory config. Knuth Vol 3 Sect 5.4.1 has the details for those who care! -- Blair Phillips, Email: blairp@spirit.net.au Canberra, Australia. Phone: +61 411189724