Is sort in Ruby stable?

Question

Is sort in Ruby stable? That is, for elements that are in a tie for sort, is the relative order among them preserved from the original order? For example, given:

a = [   {id: :a, int: 3},   {id: :b, int: 1},   {id: :c, int: 2},   {id: :d, int: 0},   {id: :e, int: 1},   {id: :f, int: 0},   {id: :g, int: 1},   {id: :h, int: 2}, ] 

is it guaranteed that we always get for

a.sort_by{|h| h[:int]} 

the following

[   {id: :d, int: 0},   {id: :f, int: 0},   {id: :b, int: 1},   {id: :e, int: 1},   {id: :g, int: 1},   {id: :c, int: 2},   {id: :h, int: 2},   {id: :a, int: 3}, ] 

without any variation for the relative order among the elements with the :id value :d, :f, and among :b, :e, :g, and among :c, :h? If that is the case, where in the documentation is it described?

This question may or may not have connection with this question.

Answer 1

Both MRI's sort and sort_by are unstable. Some time ago there was a request to make them stable, but it was rejected. The reason: Ruby uses an in-place quicksort algorithm, which performs better if stability is not required. Note that you can still implement stable methods from unstable ones:

module Enumerable   def stable_sort     sort_by.with_index { |x, idx| [x, idx] }   end    def stable_sort_by     sort_by.with_index { |x, idx| [yield(x), idx] }   end end 

Answer 2

No, ruby's built-in sort is not stable.

If you want stable sort, this should work. You probably want to create a method for it if you're going to use it often.

a.each_with_index.sort_by {|h, idx| [h[:int], idx] }.map(&:first) 

Basically it keeps track of the original array index of each item, and uses it as a tie-breaker when h[:int] is the same.

More info, for the curious:

As far as I know, using the original array index as the tie-breaker is the only way to guarantee stability when using an unstable sort. The actual attributes (or other data) of the items will not tell you their original order.

Your example is somewhat contrived because the :id keys are sorted ascending in the original array. Suppose the original array were sorted descending by :id; you'd want the :id's in the result to be descending when tie-breaking, like so:

[  {:id=>:f, :int=>0},  {:id=>:d, :int=>0},  {:id=>:g, :int=>1},  {:id=>:e, :int=>1},  {:id=>:b, :int=>1},  {:id=>:h, :int=>2},  {:id=>:c, :int=>2},  {:id=>:a, :int=>3} ] 

Using the original index will handle this too.

Update:

Matz's own suggestion (see this page) is similar, and may be slightly more efficient than the above:

n = 0 ary.sort_by {|x| n+= 1; [x, n]}