Merge sort

merge_sort_recur.rb

def mergesort arr

  def merge arr1, arr2
  
    arr = []
    j = 0
    i = 0
    while (i != arr1.size) && (j != arr2.size)
      if arr1[i] < arr2[j]
        arr << arr1[i]
        i = i+1
      elsif arr1[i] == arr2[j]
        arr << arr1[i]
        arr << arr2[j]
        i = i+1
        j = j+1
      else
        arr << arr2[j]
        j = j+1
      end
    end
    
    if i == arr1.size
      arr2[j..-1].each { |m| arr << m }
    end
    
    if j == arr2.size
      arr1[i..-1].each { |m| arr << m }
    end
    
    return arr
  end
  
  if arr.size > 2
    arr1 = mergesort arr[0..arr.size/2]
    arr2 = mergesort arr[arr.size/2+1..-1]
    return merge(arr1,arr2)
  else
    return arr if arr.size == 1
    if arr[0] > arr[1]
      arr[0], arr[1] = arr[1], arr[0]
    end
    return arr
  end
  
end