Merge two ordered arrays into one ordered array

Question

I am writing a method that takes two sorted arrays and I want it to return a merged array with all the values sorted. Given the two arrays below:

array_one = [3, 4, 8]
array_two = [1, 5, 7]

I want my merge_arrays method to return:

[1, 3, 4, 5, 7, 8]

My current algorithm is below:

def merge_arrays(array_one, array_two)
  merged_array_size = array_one.length + array_two.length
  merged_array = []

  current_index_on_one = 0
  current_index_on_two = 0
  current_merged_index = 0

  for i in (0..merged_array_size - 1)
    if array_one[current_index_on_one] < array_two[current_index_on_two]
      merged_array[current_merged_index] = array_one[current_index_on_one]
      current_index_on_one += 1
      current_merged_index += 1
    else
      merged_array[current_merged_index] = array_two[current_index_on_two]
      current_index_on_two += 1
      current_merged_index += 1
    end
  end

  return merged_array
end

I am getting an error 'undefined method `<' for nil:NilClass'. I don't understand how the conditional is receiving this. I debugged the variables in the conditionals and they are giving true or false values. I'm not sure what is causing this error.

Answer 1

arr1 = [3, 4, 8,  9, 12]
arr2 = [1, 5, 7,  8, 13]

arr = [arr1, arr2]
idx = [0, 0]

(arr1.size + arr2.size).times.with_object([]) do |_,a|
  imin = [0, 1].min_by { |i| arr[i][idx[i]] || Float::INFINITY }
  a << arr[imin][idx[imin]]
  idx[imin] += 1
end
  #=> [1, 3, 4, 5, 7, 8, 8, 9, 12, 13]

Answer 2

I made slight changes to your code in order to make it work. See the comments inside.

array_one = [2, 3, 4, 8, 10, 11, 12, 13, 15]
array_two = [1, 5, 6, 7, 9, 14]

def merge_arrays(array_one, array_two) 
  array_one, array_two = array_two, array_one if array_one.length > array_two.length # (1) swap arrays to make satement (3) work, need array_two always be the longest
  merged_array_size = array_one.length + array_two.length
  merged_array = []

  current_index_on_one = 0
  current_index_on_two = 0
  current_merged_index = 0

  for i in (0...merged_array_size-1) # (2) three points to avoid the error
    if (!array_one[current_index_on_one].nil? && array_one[current_index_on_one] < array_two[current_index_on_two]) # (3) check also if array_one is nil
      merged_array[current_merged_index] = array_one[current_index_on_one]
      current_index_on_one += 1
      current_merged_index += 1
    else
      merged_array[current_merged_index] = array_two[current_index_on_two]
      current_index_on_two += 1
      current_merged_index += 1
    end
  end
  merged_array[current_merged_index] = array_one[current_index_on_one] || array_two[current_index_on_two] # (4) add the missing element at the end of the loop, looks what happen if you comment out this line
  return merged_array
end

p merge_arrays(array_one, array_two)
# => [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15]

The error was coming because the loop was making one step over. The solution is to stop before and insert the missing element at the end of the loop.

It works also with:

# for i in (1...merged_array_size)
# and
# for i in (1..merged_array_size-1)
# and
# (merged_array_size-1).times do

Answer 3

I am getting an error 'undefined method `<' for nil:NilClass'. I don't understand how the conditional is receiving this.

You start by comparing index 0 to index 0:

[3, 4, 8]   [1, 5, 7]
 0-----------0          #=> 3 < 1

Then you increment the lower value's index by 1:

[3, 4, 8]   [1, 5, 7]
 0--------------1       #=> 3 < 5

And so on:

[3, 4, 8]   [1, 5, 7]
    1-----------1       #=> 4 < 5

[3, 4, 8]   [1, 5, 7]
       2--------1       #=> 8 < 5

[3, 4, 8]   [1, 5, 7]
       2-----------2    #=> 8 < 7

At that point you get:

[3, 4, 8]   [1, 5, 7]
       2--------------3 #=> 8 < nil

Index 3 is outside the array's bounds, so array_two[current_index_on_two] returns nil and:

if array_one[current_index_on_one] < array_two[current_index_on_two]
  # ...
end

becomes

if 8 < nil
  # ...
end

resulting in ArgumentError(comparison of Integer with nil failed). If nil is on the left hand side, you'd get NoMethodError (undefined method `<' for nil:NilClass).

Answer 4

Assuming you have two sorted arrays. You need to create pipeline using recursion going to crunch through each array. checking at each iteration to see which value at index 0 of either array is lower, removing that from the array and appending that value to the result array.

def merge_arrays(a, b)
  # build a holder array that is the size of both input arrays O(n) space
  result = []

  # get lower head value
  if a[0] < b[0]
    result << a.shift
  else
    result << b.shift
  end

  # check to see if either array is empty
  if a.length == 0
    return result + b
  elsif b.length == 0
    return result + a
  else
    return result + merge_arrays(a, b)
  end
end 

> a = [3, 4, 6, 10, 11, 15]
> b = [1, 5, 8, 12, 14, 19]
> merge_arrays(a, b)
#=> [1, 3, 4, 5, 6, 8, 10, 11, 12, 14, 15, 19]

Answer 5

Maybe I am missing the point but you can do:

(array_one + array_two).sort
=> [1, 3, 4, 5, 7, 8]

Answer 6

Here's one way you can write merge using recursion. Note, as you specified, both inputs must already be sorted otherwise the output will be invalid. The inputs can vary in size.

def merge (xs, ys)
  if xs.empty?
    ys
  elsif ys.empty?
    xs
  else
    x, *_xs = xs
    y, *_ys = ys
    if x < y
      [x] + (merge _xs, ys)
    else
      [y] + (merge xs, _ys)
    end
  end
end

merge [ 1, 3, 4, 6, 8, 9 ], [ 0, 2, 5, 7 ]
# => [ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 ]