sorting - 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