From: Yukihiro Matsumoto <matz@...>
Date: 2005-03-17T13:20:09+09:00
Subject: Re: Stable sort?

Hi,

In message "Re: Stable sort?"
    on Thu, 17 Mar 2005 12:09:19 +0900, Hal Fulton <hal9000@hypermetrics.com> writes:

|1. I think the term "stable sort" is used for a sorting
|algorithm that preserves the relative order of records
|that have the same key -- correct?

I think. so.

|3. Further I believe that Ruby's standard sort is not
|stable. (Isn't it a quicksort-like thing?)

It's using quick sort algorithm, which is not stable.

|Given that, what is a good stable sort algorithm? Would
|it be too inefficient to implement in Ruby or no?

The simplest way is to use sort_by, 

  n = 0
  ary.sort_by {|x| n+= 1; [x, n]}

which is inefficient, but not too much I guess.

							matz.