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

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

[jonathan]

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/

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

[rogerpack2005]

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


It's sad that #sort on linux is "mostly stable" but on OS X is unstable [1].  It's confusing, unfortunately.
Since almost always when I do a "sort_by(&:x).sort_by(&:y)" I am looking for a stable sort.  And that's exactly the reason that java gives for defaulting to a stable sort if it's dealing with objects [2]. Might be nice to add a stable sort option, here's a fork with a timsort: https://github.com/ruby/ruby/compare/master...phluid61:timsort
benchmarks are here: https://www.ruby-forum.com/t/timsort-in-ruby/235311/7 it's slightly slower than the unstable sort.
Anyway it would be nice to at least have it around in core, and, in my mind, be the default for at least sort_by but that's up to discretion...

[1] https://github.com/crystal-lang/crystal/issues/2350#issuecomment-550188746
[2] https://stackoverflow.com/a/15154287/32453 "Stability is a big deal when sorting arbitrary objects. For example, suppose you have objects representing email messages, and you sort them first by date, then by sender. You expect them to be sorted by date within each sender, but that will only be true if the sort is stable."

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

* 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/

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

[sawadatsuyoshi]

Issue #1089 has been updated by sawa (Tsuyoshi Sawada).


rogerdpack (Roger Pack) wrote:
> It's sad that #sort on linux is "mostly stable" but on OS X is unstable [1].  It's confusing, unfortunately.

Do you really mean it's sad? Or do you mean it's said?

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

* 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/

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

[shevegen]

Issue #1089 has been updated by shevegen (Robert A. Heiler).


sawa wrote:

> Do you really mean it's sad? Or do you mean it's said?

I think he meant "sad", rather than "said", possibly due to the desire (by a ruby user)
to see that ruby behaves in the same way across different operating systems - at the
least this is what I think rogerdpack meant. :)

I myself have no particular pro/con opinion on the issue; it may be better to create
a new one, in the event that people feel strongly about it (11 years ago is quite a
long time). I can, however had, understand that ruby users would like to see ruby 
behaves in the same way whenever they use it. In that sense, ruby abstracts away
complexities and oddities of different platforms - that is convenient for a user.

I think matz and the core team also have that goal, in the sense that I remember
suggestions that were rejected in the past if it would have led to different 
behaviour on different operating systems (or disparate features, e. g. things
that would only work on linux+ruby, but not on windows+ruby or mac+ruby).

To sorting in general: some time ago the insert-order remained the same for
hashes, so that "first-in" or "last-in" could be distinguished for free. I
liked that addition. Whenever I use .each_pair on a hash, I know that the
more recent additions will, by default, appear at the "end" of the output,
if we use e. g. .each_pair combined with puts/print output. I think that
was a good change - we sort of gain additional information for free, which
can be helpful sometimes. So I think that was convenient.

On the particular issue here, I have no particular opinion, but I also think
that both murphy and rogerdpack made good points. Even then I think it is 
better to make a new proposal, as naruse suggested back then (sorry for
commenting on that old issue as well). Matz objection was very much in 
regards to speed/slow-downs, so I think new proposals should consider
any speed trade-off as well, if it may affect other ruby users and their
code.

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

* 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/