Based on http://cleancoder.posterous.com/transformation-priority-and-sorting

transformation_priority.rb

def sort(*l)
  return l if l.size < 2
  eq = l[0]
  lt = []
  gt = []
  l.each do |e|
    if e < eq
      lt << e
    end
    if e > eq
      gt << e
    end
  end
  [sort(*lt), eq, sort(*gt)].flatten
end

def assert(actual, expected)
  if actual == expected
    puts "PASS"
  else
    raise "Fail! Expected #{expected.inspect}, but got #{actual.inspect}"
  end
end

assert(sort(), [])
assert(sort(1), [1])
assert(sort(1,2), [1,2])
assert(sort(2,1), [1,2])
assert(sort(1,2,3), [1,2,3])
assert(sort(2,1,3), [1,2,3])
assert(sort(1,3,2), [1,2,3])
assert(sort(3,2,1), [1,2,3])