### Counting Sort in Ruby

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.