Top Down Merge Sort in ruby

merge_sort.rb

#################################
# Top-down recursive merge sort
#################################

#################################
# Worst-case perf O(n log n)
# Bestt-case perf O(n log n)
# Worst-case space complexity O(n)
#################################

# Uses merge sort to sort an array of any 
# objects that respond to `<`
# @param arr [Array] an un sorted array
# @return [Array] sorted array
def merge_sort(arr)
  len = arr.length
  # check the base case
  return arr if len <= 1
  half_len = len/2
  left = []
  right = []

  # split the array in half
  arr.each_with_index do |el, i|
    if i < half_len
      left << el
    else
      right << el
    end
  end

  # recursively merge_sort each half
  left = merge_sort(left)
  right = merge_sort(right)
  # merge the halves
  merge(left, right)
end

# Performs actual comparison and merges
# `left and `right` into an intermediate array
# @param left [Array] the left half
# @param right [Array] the right half
# @return [Array] and intermediate or final  sorted array
def merge(left, right)
  result = []

  while !left.empty? && !right.empty? do
    # compare the first elements for sorting
    if left[0] <= right[0]
      result << left.shift
    else
      result << right.shift
    end
  end
  
  # do the merge if anything remains in left or right
  while !left.empty? do
    result << left.shift
  end
  while !right.empty? do
    result << right.shift
  end

  result
end

a = Array.new(100) { rand(1..100) }

puts "The unsorted array"
print a
puts "\n"
n = merge_sort(a)
puts "The sorted array"
print n