Starting ground for mergesort in ruby -- with recursive and iterative solutions.

mergesort.rb

def mergesort(a)
  # if the array size is 0|1 then the list is considered sorted, return sorted
  return a if a.length <= 1

  # split the list in half
  left, right = split_array a

  # merge sort each half
  sorted_left  = mergesort left
  sorted_right = mergesort right

  # combine the sorted halves 
  # combine_recursive(sorted_left, sorted_right)
  combine_until(sorted_left, sorted_right)
end

def split_array(a)
  middle = a.length / 2
  return a.take(middle), a.drop(middle)
end

def combine_until(a, b)
  result = []

  until a.empty? || b.empty? do
    if a[0] < b[0]
      result.push a.shift
    else
      result.push b.shift
    end
  end

  result + a + b
end

def combine_recursive(a, b)
  # puts "a: #{a.inspect} | b: #{b.inspect}"
  return a if b.empty?
  return b if a.empty?

  smallest = a[0] < b[0] ? a.shift : b.shift
  combine_recursive(a, b).unshift(smallest)
end

# TEST IT
a = [6,23,53,1,2,5,62,61,33,21,14,6,23]
puts "ORIGINAL \n" + a.to_s
a = a.shuffle
a = mergesort(a)
puts "AFTER MERGESORT \n" + a.to_s

Line 33 is my favorite 😍