Two way merge (descending)

<<-DOC
  Merge two sorted lists in descending order (non-ascending)
  Working backwards and not using sentinel.
DOC
module Twowaymerge
  def merge (a,b)
    index_a = a.length-1
    index_b = b.length-1
    c=[]

    while  (index_a >= 0 and index_b >= 0)  do
      if a[index_a] >= b[index_b]
         c << a[index_a]
           index_a-=1
      else
         c << b[index_b]
           index_b-=1
      end
    end

    while  (index_a >= 0) do
       c << a[index_a]
       index_a-=1
    end

    while  (index_b >= 0) do
       c << b[index_b]
       index_b-=1
    end
    c
  end
end

cat test.rb
  load "./twowaymergerev.rb"

  include Twowaymerge

  a = [ -6, -3, 9, 100, 102, 103]

  b = [ 1, 2, 3,  4]

  puts Twowaymerge.merge(a,b)

Two way merge (sentinel)

twowaymerge.rb (w/ sentinel)

leads to less code.

<<-DOC
  Merge two sorted lists in ascending order (non-descending)
  with a sentinel. Sentinel is just a markup on the original
  lists that's a stop-indicator so that we don't rely on checking
  of the length to stow away the remaining items on the output list.
DOC
module Twowaymerge
  def merge (a,b)
    index_a = 0
    index_b = 0
    c=[]

    a.push(Float::MAX)
    b.push(Float::MAX)

    while (index_a < a.length and index_b < b.length) do
      if a[index_a] <= b[index_b] then
         c << a[index_a]
         index_a=index_a+1
      else
         c << b[index_b]
         index_b=index_b+1
      end
    end
    c.pop
    c
  end
end

Testing:

irb -r ./twowaymerge.rb
irb(main):001:0> include Twowaymerge
=> Object
irb(main):002:0> a = [2, 6, 10]
=> [2, 6, 10]
irb(main):003:0> b = [3, 9, 18]
=> [3, 9, 18]
irb(main):004:0> Twowaymerge.merge(a,b)
=> [2, 3, 6, 9, 10, 18]

Testing is the most important part of coding any algorithm. 

Main test scenarios are:

max(a) < min(b)
max(b) < min (a)
max (a) > min (b)
max (b) > min(a)

Two way merging

Given two sorted lists, write a method that would perform the merging and
provide a new sorted list.

twowaymerge.rb

 <<-DOC

  Merge two sorted lists in ascending order (non-descending)

DOC

module Twowaymerge
  def merge (a,b)
    index_a = 0
    index_b = 0
    c=[]

    while (index_a < a.length and index_b < b.length) do
      if a[index_a] <= b[index_b] then
         c << a[index_a]
         index_a=index_a+1
      else
         c << b[index_b]
         index_b=index_b+1
      end
    end

    ## Stow away any remaining
    while index_b < b.length  do
      c << b[index_b]
      index_b=index_b+1
    end
    while index_a < a.length  do
      c << a[index_a]
      index_a=index_a+1
    end
  end
end

Testing:

irb -r ./twowaymerge.rb

irb(main):001:0> include Twowaymerge
=> Object
irb(main):002:0> a = [ 3, 5, 9]
=> [3, 5, 9]
irb(main):003:0> b = [ 1 ,2, 6]
=> [1, 2, 6]
irb(main):004:0> Twowaymerge.merge(a,b)
=> [1, 2, 3, 5, 6, 9]