Sleep sort in ruby

sleep_sort.rb

#!/usr/bin/env ruby

# Outputs sorted args to stdout
# from:
#   http://dis.4chan.org/read/prog/1295544154/170
def sleep_sort(*args)
  args.each { |e| fork { sleep(e.to_f/1000); puts e } }
end
sleep_sort(*ARGV)

# Returns sorted array of args
def sleep_sort2(*args)
  [].tap { |a| args.map { |e| Thread.new{ sleep e.to_f/1000; a << e} }.each{|t| t.join} }
end

# usage: ruby sleep_sort.rb 1 3 51 22 372 2
puts sleep_sort2(*ARGV)

# monkeypatch array so you can do [3,12,4].sleep_sort
class Array
  def sleep_sort
    semaphore = Mutex.new
    [].tap do |a|                   # start with an empty array to hold sorted results
      self.map do |e|               # iterate over every element of this array instance
        Thread.new do               # create a Thread for each element
          sleep e.to_f/1000         # sleep longer for bigger numbers            
          semaphore.synchronize do  # wrap in Mutex to prevent race conditions
            a << e                  # wake up and add to the results array
          end
        end
      end.each do |t|               # iterate over every thread...
        t.join                      # ...and execute it
      end
    end
  end
end 

# for those who prefer a 1-liner
class Array
  def sleep_sort
    [].tap { |a| self.map { |e| Thread.new{ sleep e.to_f/1000; a << e} }.each{|t| t.join} }
  end
end

puts ARGV.sleep_sort

sleep_sort_benchmark.rb

require 'benchmark'

big_arr = []
50.times do   # use a small number to ensure results are sorted right
  big_arr << Random.rand(1000)
end

sorted = []
sleep_sorted = []

Benchmark.bm do |x|
  x.report { sorted = big_arr.dup.sort }         
  x.report { sleep_sorted = big_arr.dup.sleep_sort }
end

raise "sleep sort failed!" unless sorted == sleep_sorted
# results on ruby 1.9.2
# =>      user     system      total        real
#     0.000000   0.000000   0.000000 (  0.000026)
#     0.010000   0.010000   0.020000 (  0.997363)

s=[];ARGV.each{|a|s<<Thread.new{sleep a.to_i;puts a}};s.each{|t|t.join}

Interesting idea, c2h2. I updated the gist using Thread and also modified the method to return an array instead of just printing the numbers.

haha lols, might can expand Array methods... like

class Array
  def sleep_sort
    new=[]
    s=[];self.each{|a|s<<Thread.new{sleep a.to_i;new<<a}};s.each{|t|t.join}
    new
  end
end

Wow! You took it to the next level. I'll come back and try this out when I find some time. Thanks!

Updated the gist with a monkeypatch to Array based on c2h2's comment.

just one little tip, u dont actually need require 'thread' for nowadays ruby

Thanks, I ran a quick test and you are right. I updated the gist accordingly.