Sort stability: Difference between revisions

Line 558:

=={{header|Ruby}}==

Ruby's built-in sort methods ~~use~~ quicksort which is not stable[[http://groups.google.com/group/comp.lang.ruby/msg/2a6c50d173a902da? 1]].

Ruby's built-in sort methods (Array#sort, Array#sort_by, Enumerable#sort and Enumerable#sort_by) are not stable. [[MRI]] uses [[Sorting algorithms/Quicksort|quicksort]], which is not stable [http://groups.google.com/group/comp.lang.ruby/msg/2a6c50d173a902da? (1)]. It seems that stable sorting is not worth the performance trade-off; MRI rejected a proposal to switch to a stable sort [http://redmine.ruby-lang.org/issues/show/1089 (2)].

<lang ruby>ary = [["UK", "London"], ["US", "New York"], ["US", "Birmingham"], ["UK", "Birmingham"]]

⚫

ary.sort {|a,b| a[1] <=> b[1]}

<lang ruby>ary = [["UK", "London"],

["US", "New York"],

["US", "Birmingham"],

["UK", "Birmingham"]]

⚫

p ary.sort {|a,b| a[1] <=> b[1]}

# MRI reverses the Birminghams:

# => [["UK", "Birmingham"], ["US", "Birmingham"], ["UK", "London"], ["US", "New York"]]</lang>

Other implementations of Ruby might differ. Old versions of [[JRuby]] used java.util.Arrays.sort, which is a stable sort, but is slower than MRI. To increase performance, JRuby switched to quicksort, which is not stable. [http://jira.codehaus.org/browse/JRUBY-2198 (3)]

There seems to be some discussion debating whether stable sorting is worth the performance trade-off [[http://redmine.ruby-lang.org/issues/show/1089 2]].

<!--

To code a stable sort[[http://codesnippets.joyent.com/posts/show/1698 2]]: