merge_sort.rb

#!/usr/bin/env ruby

def devide(list)
  if (list.length == 1) ; return [list]; end
  index = (list.length - 1)/2
  return [list[0..index], list[index+1..list.length-1]]
end

def merge(acc, xs, ys)
  # p "acc=#{acc}"
  # p "xs=#{xs}"
  # p "ys=#{ys}"
  if (xs.length == 0 && ys.length == 0); return acc; end
  if (xs.length == 0); return merge(acc << ys[0], [], ys[1..ys.length-1]); end
  if (ys.length == 0); return merge(acc << xs[0], xs[1..xs.length-1], []); end
  if (xs[0] < ys[0]); return merge(acc << xs[0], xs[1..xs.length-1], ys); end
  if (xs[0] == ys[0]); return merge(acc << xs[0], xs[1..xs.length-1], ys); end
  if (xs[0] > ys[0]); return merge(acc << ys[0], xs, ys[1..ys.length-1]); end
end

def sort(list)
  if (list.length == 0); return list; end
  if (list.length == 1); return list; end
  devided = devide(list)
  merge([], sort(devided[0]), sort(devided[1]))
end

# p orig = []
# p orig = [1]
p orig = [5,2,1,3,4,10,33,22,34,2,44,21,32]
p sort(orig)