In article <··········@news.nyu.edu>, ·······@barney.cs.nyu.edu (Marc Schwarz) w
rites:
>You might be confusing heapsort with something else.
>According to Sedgewick's book, "Algorithms," heapsort is, on
>average, O(N log N); O(N * N) worst case.
In fact, heapsort is quite robust. It is quicksort which is O(N^2) in the
worst case. Look at Computer Algorithms by Sara Baase page 80. The table
there gives heapsort as O(nlogn) in the general case and 2(n-1)logn in the
worst case. It also gives mergesort as O(nlogn) in general and nlogn in the
worst case. (The theta used there is a somewhat more stringent form of the
O.) A disadvantage of mergesort is the extra space requirement. For very
large lists which have to be kept on disk mergesort may be the only
practical sort. Here the disk overhead becomes a disadvantage.
S. L. Gulden
····@lehigh.edu