merge_sort.rb

# Merge Sort Implementation

# makes a recursive call on itself until the condition is met.
# merge all sub-arrays in a sorted manner
def merge_sort(array)
  # check if the array is less or equal 1, return the array.
  if array.length <= 1
    array
  else
    mid = (array.length / 2).floor # divides the array in half and recursively call the merge_sort method
    left = merge_sort(array[0..mid-1])
    right = merge_sort(array[mid..array.length])
    merge(left, right)
  end
end

def merge(left, right) # merge all sub-arrays in a sorted manner.
  if left.empty?
    right
  elsif right.empty?
    left
  elsif left[0] < right[0]
    [left[0]] + merge(left[1..left.length], right)
  else
    [right[0]] + merge(left, right[1..right.length])
  end
end