再帰

def merge(a, b)
  if a.length == 0 || b.length == 0
    a + b
  elsif a[0] < b[0]
    [a[0]] + merge(a[1..a.length-1], b)
  else
    [b[0]] + merge(a, b[1..b.length-1])
  end
end

def mergesort(a)
  if a.length <= 1
    a
  else
    last_index = a.length - 1
    half_index = last_index / 2
    merge(mergesort(a[0..half_index]),
          mergesort(a[half_index+1..last_index]))
  end
end

def quicksort(a)
  qsort(a, 0, a.length-1)
end

def qsort(a, from, to)
  if from < to
    pivot = (from + to) / 2
    med = a[pivot]
    l = from
    r = to
    while l <= r
      while a[l] < med
        l = l + 1
      end
      while a[r] > med
        r = r - 1
      end
      if l <= r
        a[l], a[r] = a[r], a[l]
        l = l + 1
        r = r - 1
      end
    end
    qsort(a, from, r)
    qsort(a, l, to)
  end
  a
end