Friday, August 30, 2013

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)

No comments:

Post a Comment