System_commands

Let’s say you have half-a-million integers in a file.. and you want to sort them.

You can write a very beautiful implementation of quicksort:

module QuickSort
  refine Array do
    def quicksort
      return [] if empty?

      pivot = delete_at(rand(size))
      left, right = partition(&pivot.method(:>))

      return *left.quicksort, pivot, *right.quicksort
    end
  end
end


numbers = File.readlines('numbers', chomp: true).map(&:to_i)

using QuickSort
numbers.quicksort
p :done

It took (on my machine) 1 minute, 13 seconds to complete.

There is also the stack.. and the number of recursive calls to consider.. IF the file would have ONE MILLION numbers.. Ruby would break (Stack level too deep).

You would have to write two implementations and let the code choose based on data.

Then the speed… I could use Crystal or C++

But there is a better way .. sort -n numbers > sorted

It takes 0.2 seconds (on my machine).