merge two sorted arrays without built in ruby function

Question

Im trying to merge two sorted arrays without using any build in sorting methods. Here is what I have so far.

def merge(array_1, array_2)
    i = 0
    k = 0
    merged_array = []
    while i < array_1.count && k < array_2.count
        while k < array_2.count && array_1[i] > array_2[k]
            merged_array << array_2[k]
            k += 1
        end
        merged_array << array_1[i]
        i += 1
    end
    merged_array
end

array_1 = [5,8,9,11]
array_2 = [4,6,7,12,13]

p merge(array_1, array_2)

The input is array_1 = [5,8,9,11] and array_2 = [4,6,7,12,13] and the output is suppose to be [4, 5, 6, 7, 8, 9, 10, 11, 12, 13]. Can someone please explain why its not working. Thank you!

Answer 1

Try this

def merge(array_1, array_2)
  return enum_for(__method__, array_1, array_2) unless block_given?

  a = array_1.each
  b = array_2.each
  loop { yield a.peek < b.peek ? a.next : b.next }

  # Your code is not working because the equivalent of these two lines
  # is missing. After you reach the end of one array you have to append
  # all remaining elements of the other array. I am doing this here by
  # just exhausting both enumerators, one of which is empty by now.

  loop { yield a.next }
  loop { yield b.next }
end

p merge([5, 8, 9, 11], [4, 6, 7, 12, 13]).entries

No need to keep track of indices. Merge sort goes back to the age of mainframes and tapes and can thus be implemented using enumerators only.

How does this work?

• each creates enumerators
• peek returns the next element without advancing the enumerator
• next returns the next element with advancing the enumerator
• both of the above raise StopIteration when they reach the end of the enumerator
• loop repeats a block of code until StopIteration is raised