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: 109fba,baaf5f793d03d420 X-Google-Attributes: gid109fba,public X-Google-Thread: 103376,97188312486d4578 X-Google-Attributes: gid103376,public X-Google-Thread: fc89c,97188312486d4578 X-Google-Attributes: gidfc89c,public X-Google-Thread: 1014db,6154de2e240de72a X-Google-Attributes: gid1014db,public From: dewar@cs.nyu.edu (Robert Dewar) Subject: Re: Teaching sorts [was Re: What's the best language to start with?] Date: 1996/08/12 Message-ID: #1/1 X-Deja-AN: 173648940 references: <31FBC584.4188@ivic.qc.ca> <01bb83f5$923391e0$87ee6fce@timpent.airshields.com> <4uah1k$b2o@solutions.solon.com> <01bb853b$ca4c8e00$87ee6fce@timpent.airshields.com> <4udb2o$7io@solutions.solon.com> <4umeot$re2@hil-news-svc-2.compuserve.com> organization: Courant Institute of Mathematical Sciences newsgroups: comp.lang.c,comp.lang.c++,comp.unix.programmer,comp.lang.ada Date: 1996-08-12T00:00:00+00:00 List-Id: Steve Heller said " Of course, if any are using radix sort, they're done well before anyone else. Why this O(n) method of sorting isn't taught more widely escapes me." Radix sorts are not O(n), the analysis is not that simple. They are O(kN) where k is the number of radix digits in the numbers, and if you use left to right (e.g. radix exchange sorting), the early termination for subsets of 1 results in an ONlogN behavior after all. Still it is quite true that a simple radix sort for cards will beat the heap and quicksort crowds :-) I agree that both radix sorts and address calculation sorts should be taught more systematically. The reason that attention tends to focus on comparison sorts is that these analyze most nicely from an academic point of view :-)