Recursive Ruby merge sort
You can define left and right in merge_sort this way:

n = m.length
if n &lt;= 1
  return m
end

left = merge_sort(m[0 ... n/2])
right = merge_sort(m[n/2 .. -1])


Depending on your Ruby version, Array#shift can be O(n). You could keep 2 indices for a and b:

def merge(a, b)
  result = []
  i, j = 0, 0
  na, nb = a.size, b.size

  while i &lt; na &amp;&amp; j &lt; nb do
    if a[i] &lt;= b[j]
      result &lt;&lt; a[i]
      i += 1
    else
      result &lt;&lt; b[j]
      j += 1
    end
  end

  return result + a[i..-1] + b[j..-1]
end


With those changes, the code becomes twice as fast with input = [*1..100000].shuffle.