Merge two sorted arrays without sorting and merging

realisation.rb

require 'benchmark'

class Array
  def insert_sorted(obj)
    shift = -1
    puts "Prepending #{obj} to #{self}"
    if self.size == 0
      puts "Adding #{obj} to the end of #{self}"
      self << obj
      puts "Got #{self}"
      inserted = true  
    end
    self.size.times do
      inserted = false
      element = self[shift]
      pre_element = self[shift-1]
      puts "Trying #{obj} between #{pre_element} and #{element}"
      if (element && pre_element)
        if (pre_element..element).include? obj
          if obj != element && obj != pre_element
            puts "Pushing #{obj} to #{self} with index #{shift}"
            self.insert(shift-1, obj)
            puts "Got #{self}"
            inserted = true
          else
            puts "#{obj} equals to #{element} or #{pre_element}. Skipping"
            return
          end
        elsif obj > element
          puts "Adding #{obj} to the end of #{self}"
          self << obj
          puts "Got #{self}"
          inserted = true  
        else
          puts "No place to insert. Going deeper."
        end
      elsif (obj <=> element) == 1
        puts "Prepending #{element} with #{obj}"
        self.insert(shift, obj)
        puts "Got #{self}"
        inserted = true
      elsif (obj <=> element) == -1
        puts "Pre-Prepending #{element} with #{obj}"
        self.insert(shift-1, obj)
        puts "Got #{self}"
        inserted = true
      else
        puts "No actions taken"
        return
      end
      return if inserted
      shift -= 1
      puts "Increasing depth to #{shift}"
    end
  end
end

def join_arrays_third(first_array, second_array)
  out = []
  first_array.each do |e|
    out.insert_sorted e
  end
  second_array.each do |e|
    out.insert_sorted e
  end
  out
end

cases = [
  [[1,4],[2,3]],
  [[1,2,3], [1,2,3]],
  [[1,2,3], [4,5,6]],
  [[1,4,5], [4,5,6,7]],
  [[1,4,5,10,12,13], [1,4,5,6,7]],
  [[100,150,300],[1,2,3,4,5,6]],
  [[0,1,9,10,22],[500,1000]],
  [[0],[-1]],
  [[0],[-3,-2,-1]],
  [[1], [1]],
  [[1,1,1,2,3,4], [100,100,100,400]],
]

def puts(s)

end

def test_my_realisation(cases)
  cases.each do |first, second|
    result = join_arrays_third(first, second)
    test_results(first, second, result)
  end
end

def test_built_in_realisation(cases)
  cases.each do |first, second|
    result = (first | second).sort.uniq
    test_results(first, second, result)
  end
end

def test_results(first_array, second_array, result)
  sorted = (result.sort == result)
  uniq = (result == result.uniq)
  contain_both_arrays = ((first_array + second_array).sort.uniq) == result
  raise "We failed" unless (sorted && uniq && contain_both_arrays)
end

n = 5000
Benchmark.bm do |x|
  x.report('my:') { n.times{ test_my_realisation(cases) } }
  x.report('ru:') { n.times{ test_built_in_realisation(cases) } }
end

task

https://www.careercup.com/question?id=5119173588942848

Given two sorted arrays A and B that may have repeated elements.  
Form a new sorted array C that contains the elements of A and B  
[Condition : You are not allowed to merge the two arrays and then sort. ]