Randomizing an Array Revisited

It was pointed out in a comment on my post about randomizing arrays in Ruby that the sort_by{rand} is O(n log n), and it can be done in linear time, i.e. O(n). This is, of course, correct. Efficiency wasn't my primary concern in the original post, so much as a quick and easy to remember solution. That said, it's worth presenting the more complicated but more efficient algorithm.

I could just give the link to the blog post linked in the comment, but for the convenience of the reader I'll repeat the solution here (with minor changes that make me happier without changing the algorithm):

class Array
  def shuffle
    array = dup
    size.downto 2 do |j|
      r = rand j
      array[j-1], array[r] = array[r], array[j-1]
    end
    array
  end
end

Enjoy!