Path: utzoo!attcan!uunet!samsung!usc!zaphod.mps.ohio-state.edu!tut.cis.ohio-state.edu!att!cbnewsk!ech
From: ech@cbnewsk.ATT.COM (ned.horvath)
Newsgroups: comp.sys.mac.programmer
Subject: Heapsort
Message-ID: <2368@cbnewsk.ATT.COM>
Date: 6 Apr 90 22:12:57 GMT
References: <1990Apr5.150213.14655@ux1.cso.uiuc.edu>
Organization: AT&T Bell Laboratories
Lines: 26

From article <1990Apr5.150213.14655@ux1.cso.uiuc.edu>, by dorner@pequod.cso.uiuc.edu (Steve Dorner):

> But it requires other space overhead that QuickSort does not; either explicit
> heap pointers, or a table that is (potentially) twice as large as it has
> to be (if n is a power of 2 or slightly more).  Or is my memory failing?
> 
> One advantage that has gone unmentioned is that Heapsort is stable; it doesn't
> change the order of equal keys.  Quicksort is decidedly unstable, which can
> be a BAD THING.

Heapsort uses only fixed space for its index variables (a purist would
say O(logN) since an index needs logN bits for an array of size N),
assuming you're sorting an array of fixed-size objects.  Since that's
what qsort operates on, I assume that's the name of the game.

Heapsort operates on arrays of arbitrary size, not just sizes near 2^n.

Heapsort is NOT stable.  Neither is Quicksort.  I know of no "tweaks"
to either that are.

Straight-insertion sort is stable, but may be O(N^2).  I know a simple 
recursive in-place stable sort, but it's O(N(logN)^2).  I know an NlogN
inplace stable sort that's so hairy it got me a PhD back in the 70's...
(you DON'T want to know).

=Ned Horvath=