#gunmacs MergeSort

gistfile1.rb

require 'pry'
require 'test/unit'

class Array
  def merge_sort
    ary = self.dup
    return ary if size <= 1

    mid = size / 2
    left = ary[0, mid]
    right = ary[mid, size]

    left.merge_sort.merge(right.merge_sort)
  end

  def merge(target)
    left = self.dup
    right = target.dup
    result = []

    while (left != [] || right != [])
      if left == []
        result << right.shift
      elsif right == []
        result << left.shift
      else
        n = (left.first <= right.first) ? left.shift : right.shift
        result << n
      end
    end

    result
  end
end

class ArrayTest < Test::Unit::TestCase
  def test_merge_sort
    assert_equal([], [].merge_sort)
    assert_equal([1], [1].merge_sort)
    assert_equal([1, 2], [2, 1].merge_sort)
    assert_equal([1, 2, 3, 4], [2, 4, 3, 1].merge_sort)
    assert_equal([1, 2, 3, 4, 5], [5, 2, 4, 3, 1].merge_sort)
  end

  def test_merge
    assert_equal([1, 2], [1].merge([2]))
    assert_equal([1, 2, 3, 4], [1, 2].merge([3, 4]))
    assert_equal([1, 2, 3, 4, 5, 6], [3, 5, 6].merge([1, 2, 4]))
  end
end