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: 1014db,6154de2e240de72a X-Google-Attributes: gid1014db,public X-Google-Thread: fc89c,97188312486d4578 X-Google-Attributes: gidfc89c,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/18 Message-ID: #1/1 X-Deja-AN: 175404273 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> <4v2fb9$lpj@news.utdallas.edu> <4v63jv$iqp@news.utdallas.edu> <4v7ro4$ac@news.utdallas.edu> organization: Courant Institute of Mathematical Sciences newsgroups: comp.lang.c,comp.lang.c++,comp.unix.programmer,comp.lang.ada Date: 1996-08-18T00:00:00+00:00 List-Id: Steve Heller said " Well, let's see. If we have 2**24 elements of 32 bits each to sort, and we sort the keys two bytes at a time (64K elements in the counting table), then we have two passes to count and two to sort, so K is four. On the other hand, logN, for base 2, is 24. The latter is clearly 6 times the former, if the same time is required per operation, and I suspect that the operations in the distribution counting sort (especially the counting passes) are less complex than those in quicksort or heapsort. " The distribution counting sort is quite different from a right to left radix sort (the latter being the sort you do on a sorting machine for 80 column cards, if people still remember!) My comment was on the latter, so Steve's comment on the former is quite right, but they are two different algorithms.