From: Charles Oliver Nutter <headius@...>
Date: 2010-11-19T15:43:43+09:00
Subject: Re: sort_by is not stable ?

On Sun, Nov 7, 2010 at 3:37 PM, John W Higgins <wishdev@gmail.com> wrote:
> As to the concept of whether or not another algorithm should be used - it's
> rather interesting to look here -
> http://redmine.ruby-lang.org/issues/show/1089 and especially the comments of
> Mr. Nutter who while working on JRuby had an apparently clean canvas to work
> with and still went with an unstable sort. It's sparse on details and I'm
> not trying to put words in his mouth either.

I can clarify.

JRuby used to just use the JVM-provided mergesort, which was stable
but markedly slower than Ruby 1.8.6/7's unstable quicksort. Because we
got a couple reports about sort being slower, we opted to do the
"wrong thing" and have a contributor implement a hybrid sort that
performed better than Ruby 1.8.6/7 but was unstable.

About a month later, someone raised the issue about MRI not having a
stable sort, and it was decided to make it stable. AARGH. I have not
kept up with discussions, however, and I believe sorts are still
unstable in 1.9.2, correct?

At this point I almost want there to be both options, since our
contributor (qbproger ... sorry man, your name escapes me at the
moment!) went to a lot of effort to get our current sort running well.

In any case, it wasn't an arbitrary decision. We debate almost
endlessly over these sorts of things, and I think I've taken a good
ten years off my life due to the related stress :)

- Charlie