Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!uunet!intercon!news
From: amanda@mermaid.intercon.com (Amanda Walker)
Newsgroups: comp.sys.mac.programmer
Subject: Re: Heapsort
Message-ID: <1990Apr9.045225.6895@intercon.com>
Date: 9 Apr 90 04:52:25 GMT
References: <1990Apr5.150213.14655@ux1.cso.uiuc.edu> <2368@cbnewsk.ATT.COM>
Sender: usenet@intercon.com (USENET The Magnificent)
Reply-To: amanda@mermaid.intercon.com (Amanda Walker)
Organization: InterCon Systems Corporation, Herndon, VA
Lines: 29

In article <2368@cbnewsk.ATT.COM>, ech@cbnewsk.ATT.COM (ned.horvath) writes:
> Heapsort is NOT stable.  Neither is Quicksort.  I know of no "tweaks"
> to either that are.

As several people have pointed out to me in email, heapsort is not an
inherently stable sort.  I tend to forget this, because there is a class
of cases where it can be easily made so, and most of my applications of
sorting have fallen into this class.  To wit:

Heapsort (and, in fact, almost any sorting algorithm) can be made stable
as long as you have a way to determine the original ordering of two elements
that compare as "equal", and you use this ordering to break any ties.
In my case, I usually sort an array of pointers to my actual data elements,
which are usually contiguous.  This means that I can compare the values of
the pointers themselves to determine the original ordering of any pair of
elements, thus breaking the tie and making the sort stable.  This amounts
to using a comparison function that never actually returns "equal", making
the inherent stability of the sorting algorithm irrelevant.  Since I build
the arrays of pointers anyway (principally for increased speed, since
exchanges only use pointers instead of exchanging actual data elements),
I get get stability pretty much for "free".  Note that building an index
of this sort (pun? what pun?) only requires space and time proportional
to the number if elements.

--
Amanda Walker, InterCon Systems Corporation
--
"Y'know, you can't have, like, a light, without a dark to stick it in...
 You know what I'm sayin'?"     --Arlo Guthrie