sort.rb

require 'benchmark'

def split(array)
  middle = array.length / 2
  [array[0..(middle-1)], array[middle..-1]]
end

def merge(a, b)
  i = j = 0
  result = []
  while (i < a.count || j < b.count)
    na = a[i]
    nb = b[j]
    if i < a.count && (!nb || nb > na)
      result << na
      i += 1
    elsif j < b.count
      result << nb
      j += 1
    end
  end

  if i < a.count
    result << a[i]
  elsif j < b.count
    result << b[j]
  end

  result
end

def merge_sort(ar)
  return ar if ar.length <= 1
  first, second = split(ar)
  first = merge_sort(first)
  second = merge_sort(second)
  merge(first, second)
end

def selection_sort(ar)
  (0..ar.size-2).each do |i|
    (i..ar.size-1).each do |j|
      if ar[i] >  ar[j]
        temp = ar[i]
        ar[i] = ar[j]
        ar[j] = temp
      end
    end
  end
end

class Array
  def to_s
    self.join(", ")
  end
end

SIZE = 100000
array = []
SIZE.times { array << Random.new.rand(SIZE) }

puts Benchmark.measure { result = merge_sort(array) }
puts Benchmark.measure { result = selection_sort(array) }