Stable Array Sorting in Ruby

Posted by Moser on 18 Sep 2008

Ruby uses some kind of Quicksort to sort its arrays. Unfortunately Quicksort is not stable. When you get sorted data from your database, which almost certainly sorts faster than anything in Ruby, you sometimes may want the data to be resorted in a stable way.

I found following snippet:

class Array
  def stable_sort
    n = 0
    sort_by {|x| n+= 1; [x, n]}
  end
end

I extended it to accept a block like the original sort method does:

class Array
  def stable_sort
    n = 0
    c = lambda { |x| n+= 1; [x, n]}
    if block_given?
      sort { |a, b|
        yield(c.call(a), c.call(b))        
      }
    else
      sort_by &c
    end
  end
end