Merge sort

merge_sort.rb

  def merge_sort(array)
    return array if array.length < 2
    mid   = array.length / 2
    left  = merge_sort(array[0, mid])
    right = merge_sort(array[mid, array.length-mid])
    merge_sorted_arrays left, right
  end

  def merge_sorted_arrays(array1, array2, merged_array=[])

    if array1.empty? || array2.empty?
      if array1.empty?
        return (merged_array << array2).flatten
      else
        return (merged_array << array1).flatten
      end
    end

    until array1.empty? || array2.empty?
      if array1.first < array2.first
        merged_array << array1.shift
      else
        merged_array << array2.shift
      end
    end

    if array1.empty? && array2.empty?
      return merged_array
    else
      merge_sorted_arrays(array1, array2, merged_array)
    end
  end



p merge_sorted_arrays([],      [])            # => []
p merge_sorted_arrays([],      [1])           # => [1]
p merge_sorted_arrays([1],     [])            # => [1]
p merge_sorted_arrays([1],     [2])           # => [1, 2]
p merge_sorted_arrays([2],     [1])           # => [1, 2]
p merge_sorted_arrays([1,3],   [2])           # => [1, 2, 3]
p merge_sorted_arrays([2],     [1,3])         # => [1, 2, 3]
p merge_sorted_arrays([1,2,3], [4])           # => [1, 2, 3, 4]
p merge_sorted_arrays([4],     [1,2,3])       # => [1, 2, 3, 4]


p merge_sorted_arrays([]         , [])        # => []
p merge_sorted_arrays([1]        , [])        # => [1]
p merge_sorted_arrays([2]        , [1])       # => [1, 2]
p merge_sorted_arrays([1,2,3]    , [])        # => [1, 2, 3]
p merge_sorted_arrays([4]        , [1,2,3])   # => [1, 2, 3, 4]
p merge_sorted_arrays([1,3]      , [2,4,5])   # => [1, 2, 3, 4, 5]
p merge_sorted_arrays([1,2,3,4,6], [5])       # => [1, 2, 3, 4, 5, 6]
p merge_sorted_arrays([1,3,4,6,7], [2,5])     # => [1, 2, 3, 4, 5, 6, 7]
p merge_sorted_arrays([2,5,6,8]  , [1,3,4,7]) # => [1, 2, 3, 4, 5, 6, 7, 8]
p merge_sorted_arrays([2,4,6,7,8], [1,3,5,9]) # => [1, 2, 3, 4, 5, 6, 7, 8, 9]