Kornelius Kalnbach wrote:
> I'd like to have stable sorting in Ruby. Stable sorting means that if two items are ==, they will retain their order in the list after sorting. In other words, stable sort does never switch two equal items.
...
> It would also be nice to minimize the number of comparisons, since method calling is expensive in Ruby.
> 
> Python is using a highly optimized implementation of a variant of merge sort, which is stable and uses very few comparisons (called Timsort after Tim Peters); maybe Ruby can adopt it for sort and sort_by:
> 
>   http://svn.python.org/projects/python/trunk/Objects/listsort.txt
> 
> Introducing stable sorting would not be a problem for old code because the order of equal items after sorting is currently not specified.

I'd love to hear why you're interested in a stable sort. In JRuby, we 
recently put in place an unstable hybrid of a couple sorts so we'd have 
competitive performance. Our original sort was exactly what you talk 
about for Python, a "pretty fast" stable modified merge sort.

I'd also be interested to see how the performance of Timsort compares to 
what's currently in Ruby and JRuby as well as compared to the built-in 
JDK sort we used before. If stable sorting is desired, we could 
certainly provide a flag or flip a bit in JRuby to provide it.