From: Charles Oliver Nutter <charles.nutter@...>
Date: 2009-02-06T23:37:16+09:00
Subject: [ruby-core:21889] Re: [Feature #1089] Stable sorting for sort and sort_by

Kornelius Kalnbach wrote:
> Charles Oliver Nutter wrote:
>> I'd love to hear why you're interested in a stable sort.
> Two use cases come to my mind where stable sort is needed. Excuse me for
> the confusing examples, but I find it always hard to talk about this topic.

Your two cases make sense to me, and are similar to reasons I gave for 
us not to abandon a stable sort. I eventually overruled myself, however, 
after more published benchmark results put us slower than Ruby 1.8 for 
array sorts. Perception is important; more important than sort 
stability, I have not decided :)

>> In JRuby, we recently put in place an unstable hybrid of a couple 
>> sorts so we'd have competitive performance. Our original sort was 
>> exactly what you talk about for Python, a "pretty fast" stable 
>> modified merge sort.
> Oh noes ^_^ How much difference did it make?

I guess we ended up going with an unstable sort because it did make a 
difference; I think keeping the sort stable makes it harder to combine 
allgorithms for different classes of list (partially sorted, reversed, 
randomized) which seemed to be key to matching MRI's sort performance. I 
raised a concern about stability, but we figured if nobody had seen 
issues in MRI nobody would care if JRuby's sort became unstable.

Perhaps this is a case where having the fast unstable sort support a 
slower, possibly ruby-based, stable sort is the way to go. In general a 
ruby-based sort performs pretty well on both JRuby and Ruby 1.9. Here's 
some recent results:

http://blog.concord.org/archives/24-Comparison-of-Ruby-1.8.6-1.9-and-JRuby-running-on-Java-1.5-1.6-and-1.7.html

It certainly wouldn't be as fast as a native sort, but perhaps that's 
not a big deal?

- Charlie