Issue #1089 has been updated by jonathanhefner (Jonathan Hefner).

Description updated

One use case I have for a stable sort is a large CSV file which is tracked in a git repository.  I have a script which loads the file, adds rows, and then sorts all rows by a particular column before writing them back to the file.  I need to minimize the git diff for the file, so I use a stable sort.  I currently use the `sort_by.with_index` technique, but it would be nice to have faster performance.  (A benchmark currently shows `sort_by.with_index` is 7x slower than just `sort_by`.)

Another use case I have is a list of tasks with optional priority.  By default, the tasks are ordered manually with no priority set.  But when a priority is set, the tasks are sorted such that higher priority tasks come first, while still preserving the manual ordering of both the prioritized and unprioritized tasks.

In addition to performance benefits, I think something like `sort_by(stable: true, &:foo)` communicates purpose more clearly than `sort_by.with_index{|x, i| [x.foo, i] }`.


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

* Author: murphy (Kornelius Kalnbach)
* Status: Rejected
* Priority: Normal
* Assignee: matz (Yukihiro Matsumoto)
* Target version: 
----------------------------------------
=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:ruby-core-request / ruby-lang.org?subject=unsubscribe>
<http://lists.ruby-lang.org/cgi-bin/mailman/options/ruby-core>