Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Path: utzoo!mnetor!uunet!husc6!hao!noao!arizona!naucse!sbw
From: sbw@naucse.UUCP (Steve Wampler)
Newsgroups: comp.misc,comp.lang.c
Subject: Re: Fast, stable, free, small sorts?
Message-ID: <463@naucse.UUCP>
Date: Thu, 24-Sep-87 17:24:04 EDT
Article-I.D.: naucse.463
Posted: Thu Sep 24 17:24:04 1987
Date-Received: Sat, 26-Sep-87 17:30:18 EDT
References: <460@naucse.UUCP> <3603@venera.isi.edu> <20029@cca.CCA.COM> <3636@venera.isi.edu>
Organization: Northern Arizona University, Flagstaff, Arizona
Lines: 14
Summary: stability isn't essential, just nice
Xref: mnetor comp.misc:1308 comp.lang.c:4510

In article <3636@venera.isi.edu>, lmiller@venera.isi.edu (Larry Miller) writes:
> In article <20029@cca.CCA.COM> g-rh@CCA.CCA.COM.UUCP (Richard Harter) writes:
> >
> >Stability is essential for sorting on multiple keys.
>               ^^^^^^^^^
> Oh come on.  Any first year data structures/algorithms student could devise
> a routine that will sort on multiple keys, and the sort does not have to be
> stable.

True.  However, without stability the sort must know it is sorting multiple
fields (that's way sort(1) on Unix has those options).  If it's to be be
more general purpose, then so far as I can tell, it must be stable.  I would
love to be shown wrong on this, as I seem to be incapable of writing a minimal
storage stable sort that is fast on large data sets.