Counting Sort in Ruby

by tofucoder

I stumbled on this article from Austin G. Walters on reddit. It’s about a C implemention of counting sort which is restricted to integers but is of complexity O(n), if the range of the elements is in the order of n. I did a quick implementation in Ruby to see if I could beat Ruby’s Array#sort. Here it is:

class Array
  def counting_sort
    min,max = self.minmax
    histo = Array.new(max-min+1,0)
    self.each { |e| histo[e-min] += 1 }
    sorted = []
    histo.each_with_index { |e,i| e.times {sorted << i+min} }
    sorted
  end
end

Turns out Array#sort is  way faster than this implementation. It’s more than twice as fast on an array of 1 million elements. I assume that Array#sort is not implemented in Ruby but in native code.