Extend the array class with merge_sort and binary_search

array_ext.rb

require 'rspec'
 
RSpec.configure do |config|
  config.mock_with :rspec
  config.color_enabled = true
end

module ArrayExt
  def merge_sort
    if self.length <= 1
      self
    else
      middle = self.length / 2
      left = self[0...middle].merge_sort
      right = self[middle...(self.length)].merge_sort
      merge(left, right)
    end
  end
  
  def binary_search(value, from = 0, to = self.length)
    middle = from + (to - from) / 2
    if self[middle] == value
      middle
    elsif to - from == 1
      nil
    elsif self[middle] < value
      self.binary_search(value, middle, to)
    else
      self.binary_search(value, from, middle)
    end
  end
  
  private 
  
  def merge(left, right)
    result = []

    left_copy = left.dup
    right_copy = right.dup
    
    while(left_copy.length * right_copy.length > 0) do
      if left_copy.first < right_copy.first
        result << left_copy.shift
      else
        result << right_copy.shift
      end
    end
    
    result + left_copy + right_copy
  end
end
  
class Array
  include ArrayExt
end

describe "ArrayExt" do
  subject { [7, 3, 6, 1, 9, 4] }

  describe "#merge_sort" do
    it "sorts the array" do
      subject.merge_sort.should eq([1, 3, 4, 6, 7, 9])
    end
  end

  describe "#binary_search" do
    subject(:sorted_array){ [1, 3, 4, 6, 7, 9] }

    it "returns the element position you are searching for" do
      sorted_array.binary_search(7).should eq(4)
    end
    
    it "returns nil if element is not found" do
      sorted_array.binary_search(8).should be_nil
    end
  end
end