From: Brian Candler <B.Candler@...>
Date: 2003-08-01T02:09:45+09:00
Subject: Re: Feature request: stable sort

On Thu, Jul 31, 2003 at 10:48:49PM +0900, nobu.nokada@softhome.net wrote:
> Hi,
> 
> At Thu, 31 Jul 2003 21:54:31 +0900,
> Brian Candler wrote:
> > I've just been poking around and I see that ruby's sort is implemented by
> > calling its own implementation of qsort()
> > 
> > This is fine except that qsort is not a 'stable' sort - i.e. elements with
> > equal keys do not have their existing order preserved.
> 
> It's a well known trade-off.  Fast sorts are unstable or need
> work area.
> 
> I guess it is not required as stable in all cases.  How about
> new methods, #stable_sort and #stable_sort!?

Yes, new methods would be fine. Perhaps if you use mergesort it should just
be called "mergesort". I believe it could give better performance where the
input is already partially sorted (e.g. two sorted arrays concatenated), so
you might want to choose it even if stability isn't important.

Also, doesn't quicksort have some nasty input cases where it degrades to
O(n^2), or am I thinking of something else?

Regards,

Brian.