From: John W Higgins <wishdev@...>
Date: 2010-11-08T06:37:06+09:00
Subject: Re: sort_by is not stable ?

--001485f1db98c73ac804947d4e67
Content-Type: text/plain; charset=ISO-8859-1

Good Afternoon

On Sun, Nov 7, 2010 at 1:00 PM, w_a_x_man <w_a_x_man@yahoo.com> wrote:

> On Nov 7, 12:34 pm, John W. Higgins <wish...@gmail.com> wrote:
>
> > I'd rather have the efficient implementation that one can easily make
> stable
> > by using the secondary comparison (as you can easily do in this case)
> than
> > an inefficient version that really accomplishes nothing that the
> efficient
> > version cannot.
>
> I'd rather have a stable and efficient sort.  If Python can do it,
> then there's no excuse for Ruby.
>

First, there are two issues here - one is whether or not to use quicksort as
the default sort and then whether or not there is an expectation as to
whether or not quicksort should be stable.

The issue I took was the statement that Ruby's quicksort was "badly coded".
This is not a correct statement given the many other instances of quicksort
that follow the same principal as Ruby's version in that it's not stable. I
think Ruby is just fine with respect to its quicksort implementation.

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.

Again, anyone is free to put a patch on the table and really start a good
conversation as to how it would fit in - and quite possibly a stable_sort
method would be an outstanding option here. But there just is a huge
difference between someone coming to the table patch in hand to begin a
conversation - and just saying Ruby is "badly coded". This is a sort
algorithm - it shouldn't be rocket science for someone to create a different
algorithm patch if they wanted to. There are plenty of C reference
implementations available as starting points.

John

--001485f1db98c73ac804947d4e67--