@merges = 0
@merge_sorts = 0

def merge(left, right)
  @merges += 1
  result = []
  while(left.size > 0 || right.size > 0)
    if(left.size > 0 && right.size > 0)
      if(left[0] <= right[0])
        first, *rest = *left
        result << first
        left = rest
      else
        first, *rest = *right
        result << first
        right = rest
      end
    elsif(left.size > 0)
      first, *rest = *left
      result << first
      left = rest
    elsif(right.size > 0)
      first, *rest = *right
      result << first
      right = rest
    end
  end
  result
end

def merge_sort(m)
  @merge_sorts += 1
  return m if(m.size <= 1)
  left, right = [], []
  middle = m.size / 2
  m[0..(middle-1)].each { |x| left << x }
  m[middle..-1].each {|x| right << x}

  left.replace(merge_sort(left))
  right.replace(merge_sort(right))

  merge(left, right)
end

va = 50.times.collect {|x| rand(100)}.uniq

puts "initial: " + va.inspect
puts "final: " + merge_sort(va).inspect
puts "merges: " + @merges.to_s
puts "merge_sorts: " + @merge_sorts.to_s