From: Hal Fulton <hal9000@...>
Date: 2005-03-17T12:42:11+09:00
Subject: Re: Stable sort?

Patrick Hurley wrote:
> 
>>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.

Yes, I see what you mean.

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

Yes... I always had one handy, but now I don't. I should actually
buy one.

Anyone ever implemented mergesort in Ruby? Got one handy?


Hal