mergesort

a=[52, 0, 1, 92, 93, 83, 29, 99, 48, 13, 24, 28, 68, 17, 19, 82, 67, 14, 22, 85]

def a.merge_sort(&cond)
  cond = proc{|x,y| x<y} unless cond
  mc(self,cond)
end

def a.mc(arr,cond)
  return arr if arr.size==1
  
  m = arr.size/2
  merge(mc(arr[0..m-1],cond), mc(arr[m..-1],cond), cond)
end

def a.merge(l,r,cond)
  result = []
  until l.empty? or r.empty?
    result << (cond[l[0],r[0]]? l : r).shift
  end
  result.concat(l.empty? ? r : l)
end

#test
#sortメソッドを適用した後と同じ値になるか調べる
def same? target, result
  result == target.sort
end
p same?(a, a.merge_sort)
#=>true