Recursive Ruby merge sort I have implemented a merge sort in Ruby. (Yes, I know, there's Array#sort) I would like to get feedback on code quality and optimization.

def merge(a, b)
  result = []

  while !a.empty? &amp;&amp; !b.empty?
    if a[0] &lt;= b[0]
      result &lt;&lt; a.shift
    else
      result &lt;&lt; b.shift
    end
  end

  result += a += b

  return result
end

def merge_sort(m)
  if m.length &lt;= 1
    return m
  end

  left, right = [], []
  m.each_with_index do |x, i|
    if i &lt; m.length / 2
      left &lt;&lt; x
    else
      right &lt;&lt; x
    end
  end
  left = merge_sort(left)
  right = merge_sort(right)

  return merge(left, right)
end

input = [*1..100].shuffle

p input

p merge_sort input
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.