[ruby-core:97591] [Ruby master Feature#1089] Stable sorting for sort and sort_by

Issue #1089 has been updated by rogerdpack (Roger Pack).


"sad"

It's just surprising that "depending on OS" sometimes sort is always stable.  Then occasionally isn't.  Without it nested `sort_by`'s don't work as you'd expect (secondary, tertiary sort), without high performance hit of the #with_index trick (and high cognitive hit LOL).  Java uses stable sort for objects for just this reason, FWIW.  I don't quite feel qualified to do a new ticket :| ... Cheers!

----------------------------------------
Feature #1089: Stable sorting for sort and sort_by
https://bugs.ruby-lang.org/issues/1089#change-84774

* Author: murphy (Kornelius Kalnbach)
* Status: Rejected
* Priority: Normal
* Assignee: matz (Yukihiro Matsumoto)
----------------------------------------
=begin
 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.
 
 In Ruby 1.9.1, you'd have to use something like
 
   enum.sort_by.with_index { |a, i| [a, i] }
 
 to achieve a stable sort in Ruby.
 
 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.
=end




-- 
https://bugs.ruby-lang.org/

Unsubscribe: <mailto:[e-mail]?subject=unsubscribe>
<http://lists.ruby-lang.org/cgi-bin/mailman/options/ruby-core>