From: Patrick Hurley <phurley@...>
Date: 2005-03-17T12:21:24+09:00
Subject: Re: Stable sort?

> 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?

Yup

> 2. Further I believe that such an algorithm could be used
> to implement multi-key sorts as "chained" sorts -- correct?
>       people.sort(:name).sort(:age).sort(:height)

Sure, but I am guessing you would want to reverse the order of the sorting.

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

Not sure, but quicksorts are not stable

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

Mergesort is a good choice. Efficency should be reasonable depending
upon data set sizes. Therea re of course other possiblities. When in
doubt:

D. E. Knuth. The Art of Computer Programming, Volume 3: Sorting and
Searching. Addison-Wesley, Reading MA, 1973.