Sleep Sort in Ruby

Overview

Sleep Sort is humorous algorithm allegedly posted anonymously to 4chan. It involves iterating through the array and firing off a new process for each element. In this process a sleep command is given with a time proportional to the value of the element. When these processes complete, they add their value to the sorted array in order of how long they slept.

Concise

def sleep_sort(a)
  t = []
  s = []

  a.each do |i|
    t << Thread.new { 
      sleep(i)
      s << i
    }
  end

  t.each do |i|
    i.join
  end

  s
end

u = (0..9).to_a.sort{ rand() - 0.5 }[0..9]
p u

s = sleep_sort(u)
p s
sleep_sort.rb

Verbose

# Sleep Sort
#
# Input: A sequence of numbers in any order.
# Output: An ordered sequence from smallest number to largest.
#
def sleep_sort(numbers)
  threads = []
  sorted = []

  # Iterate through the array and create a new thread for each value.
  # Inside each thread, sleep for the number of seconds represented by
  # the value of the element. Then add the number to the sorted array.
  numbers.each do |number|
    threads << Thread.new { 
      sleep(number)
      sorted << number 
    }
  end

  # Calling `join` means the main thread won't finish until every child
  # thread has finished. Otherwise the program will finish before our
  # threads are done sleeping, and the array won't be sorted.
  threads.each do |thread|
    thread.join
  end

  sorted
end

# Generate array of ten random integers.
unsorted = (0..9).to_a.sort{ rand() - 0.5 }[0..9]
puts unsorted.inspect

# Sort.
sorted = sleep_sort(unsorted)
puts sorted.inspect
sleep_sort_verbose.rb

Sample Input and Output

$ ruby sleep_sort.rb
[5, 9, 6, 2, 8, 0, 4, 3, 7, 1]
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

Further Reading