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: fc89c,97188312486d4578 X-Google-Attributes: gidfc89c,public 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 From: dewar@cs.nyu.edu (Robert Dewar) Subject: Re: Teaching sorts [was Re: What's the best language to start with?] Date: 1996/08/14 Message-ID: #1/1 X-Deja-AN: 174075968 references: <31FBC584.4188@ivic.qc.ca> <01bb83f5$923391e0$87ee6fce@timpent.airshields.com> <839708378snz@genesis.demon.co.uk> organization: Courant Institute of Mathematical Sciences newsgroups: comp.lang.c,comp.lang.c++,comp.unix.programmer,comp.lang.ada Date: 1996-08-14T00:00:00+00:00 List-Id: Robert Eachus says " It means that when you finish the first stage of the Quicksort, you have several piles laid out on the table. Completing the sort requires picking them up in order. For heap sort, building the heap is also an O(n log n) operation, since you maintain a heap. However picking up the cards is also N log N since you have to maintain the heap property, and in any case you pick them up one at a time." A surprising slip :-) Building a heap is a worst case O(N) process. I have seen it occasionally misdescribed in a form that would be N logN, but if you look at the original treesort3, you will see that the heap building phase is clearly linear (the proof is straightforward, I can share it offline if you like).