Merge Sort - Ruby Solution

merge_sort.rb

def merge(left, right, a)
  i, j, k = 0, 0, 0

  while(i < left.length && j < right.length) do
    if left[i] <= right[j]
      a[k] = left[i]
      i += 1
    else
      a[k] = right[j]
      j += 1
    end
    k += 1
  end

  while(i < left.length) do
    a[k] = left[i]
    i += 1
    k += 1
  end

  while(j < right.length) do
    a[k] = right[j]
    j += 1
    k += 1
  end

  return a
end

def merge_sort(a)
  return a if a.length < 2

  n = a.length
  mid = n / 2

  left = a[0..(mid-1)]
  right = a[mid..(n-1)]

  left = merge_sort(left)
  right = merge_sort(right)

  merge(left, right, a)
end


a = [2, 4, 1, 6, 8, 5, 3, 7]
b = [8, 7, 6, 5, 4, 3, 2, 1, 0]
puts "#{a} after Merge Sorting: #{merge_sort(a)}"
puts "#{b} after Merge Sorting: #{merge_sort(b)}"