merge sort

require 'minitest/autorun'

class Algo
  def merge_sort a
    if a.size > 1
      m = a.size / 2
      n = a.size - m
      a1 = []
      a2 = []
      0.upto(m - 1) do |i|
        a1[i] = a[i]
      end
      0.upto(n - 1) do |i|
        a2[i] = a[m + i]
      end

      merge_sort(a1);

      puts "before merge_sort. a2: #{a2.inspect}"
      merge_sort(a2);
      puts "after merge_sort. a2: #{a2.inspect}"

      merge(a1, a2, a);
    end

    a
  end

  def merge(a1, a2, a)
    i = 0
    j = 0
    while i < a1.size || j < a2.size
      if j >= a2.length || (i < a1.length && a1[i] < a2[j])
        a[i+j] = a1[i]
        i += 1
      else
        a[i+j] = a2[j]
        j += 1
      end
    end
  end
end

#---minitest---

describe Algo do
  before do
    @algo = Algo.new
  end

  describe "merge sort" do
    it "sort an array" do
      arr = [3, 2, 1]
      sorted_arr = @algo.merge_sort(arr)
      assert_equal [1,2,3], sorted_arr
    end
  end
end