Is sort in Ruby stable?

Solution 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

Solution 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]}

Solution 3:

For some implementations of Ruby, sort is stable, but you shouldn't depend upon it. Stability of Ruby's sort is implementation defined.

What the documentation says

The documentation says that you should not depend upon sort being stable:

The result is not guaranteed to be stable. When the comparison of two elements returns 0, the order of the elements is unpredictable.

Note that this does not say whether or not the sort is stable. It just says it is not guaranteed to be stable. Any given implementation of Ruby could have a stable sort and still be consistent with the documentation. It could also have an unstable sort, or change whether the sort is stable at any time.

What Ruby actually does

This test code prints true if Ruby's sort is stable, or false if it is not:

Foo = Struct.new(:value, :original_order) do
  def <=>(foo)
    value <=> foo.value
  end
end

size = 1000
unsorted = size.times.map do |original_order|
  value = rand(size / 10)
  Foo.new(value, original_order)
end
sorted = unsorted.sort
stably_sorted = unsorted.sort_by do |foo|
  [foo.value, foo.original_order]
end
p [RUBY_PLATFORM, RUBY_VERSION, RUBY_PATCHLEVEL, sorted == stably_sorted]

Here are the results for all of the Rubies I have installed on my Linux box:

["java", "1.8.7", 357, false]
["java", "1.9.3", 551, false]
["x86_64-linux", "1.8.7", 374, false]
["x86_64-linux", "1.8.7", 374, false]
["x86_64-linux", "1.8.7", 376, false]
["x86_64-linux", "1.9.3", 392, false]
["x86_64-linux", "1.9.3", 484, false]
["x86_64-linux", "1.9.3", 551, false]
["x86_64-linux", "2.0.0", 643, false]
["x86_64-linux", "2.0.0", 648, false]
["x86_64-linux", "2.1.0", 0, false]
["x86_64-linux", "2.1.10", 492, false]
["x86_64-linux", "2.1.1", 76, false]
["x86_64-linux", "2.1.2", 95, false]
["x86_64-linux", "2.1.3", 242, false]
["x86_64-linux", "2.1.4", 265, false]
["x86_64-linux", "2.1.5", 273, false]
["x86_64-linux", "2.1.6", 336, false]
["x86_64-linux", "2.1.7", 400, false]
["x86_64-linux", "2.1.8", 440, false]
["x86_64-linux", "2.1.9", 490, false]
["x86_64-linux", "2.2.0", 0, true]
["x86_64-linux", "2.2.1", 85, true]
["x86_64-linux", "2.2.2", 95, true]
["x86_64-linux", "2.2.3", 173, true]
["x86_64-linux", "2.2.4", 230, true]
["x86_64-linux", "2.2.5", 319, true]
["x86_64-linux", "2.2.6", 396, true]
["x86_64-linux", "2.3.0", 0, true]
["x86_64-linux", "2.3.1", 112, true]
["x86_64-linux", "2.3.2", 217, true]
["x86_64-linux", "2.3.3", 222, true]
["x86_64-linux", "2.4.0", 0, true]
["x86_64-linux", "2.4.0", -1, true]
["x86_64-linux", "2.4.0", -1, true]
["x86_64-linux", "2.4.0", -1, true]
["x86_64-linux", "2.4.0", -1, true]
["x86_64-linux", "2.4.1", 111, true]
["x86_64-linux", "2.4.2", 198, true]
["x86_64-linux", "2.4.5", 335, true]
["x86_64-linux", "2.4.9", 362, true]
["x86_64-linux", "2.5.0", 0, true]
["x86_64-linux", "2.5.3", 105, true]
["x86_64-linux", "2.5.7", 206, true]
["x86_64-linux", "2.6.0", 0, true]
["x86_64-linux", "2.6.2", 47, true]
["x86_64-linux", "2.6.3", 62, true]
["x86_64-linux", "2.6.4", 104, true]
["x86_64-linux", "2.6.5", 114, true]
["x86_64-linux", "2.6.6", 146, true]
["x86_64-linux", "2.7.0", 0, true]
["x86_64-linux", "2.7.1", 83, true]
["x86_64-linux", "2.7.2", 137, true]
["x86_64-linux", "3.0.0", 0, true]
["x86_64-linux", "3.0.0", -1, true]
["x86_64-linux", "3.0.1", 64, true]
["x86_64-linux", "3.0.2", 107, true]

We can see that JRuby is unstable, and MRI before 2.2, on Linux, is unstable. MRI >= 2.2.0 is stable (again, on Linux).

The platform matters, though. Although the above result shows that sort is stable in MRI 2.4.1 on Linux, the same version is unstable on Windows:

["x64-mingw32", "2.4.1", 111, false]

Why is MRI's sort stable on Linux, but not on Windows?

Even within a single version of a Ruby implementation, the sort algorithm can change. MRI can use at least three different sorts. The sort routine is selected at compile time using a series of #ifdefs in util.c. It looks like MRI has the ability to use sorts from at least two different libraries. It also has its own implementation.

What should you do about it?

Since the sort may be stable but can't be guaranteed to be stable, do not write code which depends upon Ruby's sort being stable. That code could break when used on a different version, implementation, or platform.