Is high-speed sorting impossible with Ruby?

Question

I've studied the poignant guide and it really has helped me pick up the language pretty fast. After that, I started solving some coding puzzles using Ruby. It just helps a lot to get used to the language I feel.

I'm stuck with one such puzzle. I have solved it very easily since it is pretty straight-forward, but the solution is being rejected (by the host website) with the error 'Time Exceded'! I know that Ruby cannot compete with the speed of C/C++ but it has got to be able to answer a tiny puzzle on a website which accepts solutions in Ruby?

The puzzle is just a normal sort.

This is my solution

array ||= []
gets.to_i.times do
  array << gets
end
puts array.sort

My question is, is there any other way I can achieve high-speed sorting with Ruby? I'm using the basic Array#sort here, but is there a way to do it faster, even though it means lot more lines of code?

Answer 1

I've solved that problem, and let me tell you using a nlogn algorithm to pass that is almost impossible unless you are using a very optimized C/Assembly version of it.

You need to explore other algorithms. Hint: O(n) Algorithm will do the trick, even for ruby.

Good Luck.