Bottom-up merge sort in Ruby

bottom_up_merge_sort.rb

def merge_sort(a, lo, mid, hi)

  # a[lo..mid] and a[mid+1..hi] must be sorted

  dup = a.clone

  # index for the left sub-array: lo <= i <= mid
  i = lo

  # index for the right sub-array: mid+1 <= j <= hi
  j = mid+1

  # index for the sorted sub-array: lo <= k <= hi
  k = lo

  while k <= hi
    # All numbers in left sub-array have been compared
    # so copy number from the right sub-array.
    if i > mid
      a[k] = dup[j]
      j += 1

    # All numbers in right sub-array have been compared
    # so copy number from the left sub-array
    elsif j > hi
      a[k] = dup[i]
      i += 1

    # Number in right sub-array is less than the number in
    # left sub-array. So copy number from the right sub-array
    elsif dup[j] < dup[i]
      a[k] = dup[j]
      j += 1

    # Number in left sub-array is less than the number in
    # right sub-array. So copy number from left sub-array
    else
      a[k] = dup[i]
      i += 1
    end
    k += 1
  end

  # The array `a[lo..hi]` is sorted.
end

def bottom_up_merge_sort(a)
  sz = 1
  n = a.count
  while sz < n
    lo = 0

    # Ensure there are at least sz numbers to sort
    while lo < (n - sz)

      # a[lo..hi] has at most 2*sz numbers or
      # at least n-1-lo numbers
      hi = [n-1, lo+sz+sz-1].min

      # a[lo..mid] has sz numbers
      mid = lo+sz-1

      merge_sort(a, lo, mid, hi)

      lo = hi + 1
    end

    # Ensure that sz is a power of 2
    sz = sz + sz
  end
  a
end

input = [5, 2, 6, 8, 7, 3, 4, 1]
puts "#{input} => #{bottom_up_merge_sort(input)}"