Photo by John Lockwood on Unsplash

Merging Pre-Sorted Arrays in Ruby

Ruby is a magnificent programming language. There is so much maturity in its syntax and methods that are all designed to make the programmer’s life easier.

I’m a big fan of the array method in Ruby. The way they abstract the logic necessary to massage and mutate array data is amazing.

I was tasked with creating an API route that returned an array containing potentially up to 4 different objects, all sorted in descending order of date created. In addition to these requirements, the number of items in the merged array would be limited.

As it turns out, the fact that the data is comprised of different objects has very little impact on the solution’s logic.

Let’s start with 4 arrays

arr1 = [1, 3, 5, 8, 9].
arr2 = [4, 10, 12, 14, 16]
arr3 = [2, 7, 28, 35, 47]
arr4 = [3, 18, 21, 25, 40]

To account for the fact that I expect the data to be sorted in descending order, I’ll apply sort_by and reverse! methods.

arr1 = [1, 3, 5, 8, 9].sort_by { |a| a }.reverse!
arr2 = [4, 10, 12, 14, 16].sort_by { |a| a }.reverse!
arr3 = [2, 7, 28, 35, 47].sort_by { |a| a }.reverse!
arr4 = [3, 18, 21, 25, 40].sort_by { |a| a }.reverse!

Brute Force — Plus Operator

The simplest way to combine these arrays and sort them is to just the plus operator.

merged_array = arr1 + arr2 + arr3 + arr4
 => [9, 8, 5, 3, 1, 16, 14, 12, 10, 4, 47, 35, 28, 7, 2, 40, 25, 21, 18, 3]

The merged array will contain all the desired elements, but it is still unsorted.

merged_array = (arr1 + arr2 + arr3 + arr4).sort_by { |a| a }.reverse!
 => [47, 40, 35, 28, 25, 21, 18, 16, 14, 12, 10, 9, 8, 7, 5, 4, 3, 3, 2, 1]

Applying the sort_by and reverse! yields the desired result.

Finally, the array will be limited to 15 objects.

merged_array = (arr1 + arr2 + arr3 + arr4).sort_by { |a| a }.reverse![0..14]
 => [47, 40, 35, 28, 25, 21, 18, 16, 14, 12, 10, 9, 8, 7, 5]

A Better Solution — Find and Merge

Since the arrays are presorted before being merged, a more efficient solution exists which involves:

1. Finding the array with the highest value (or the winner),
2. Saving the value and removing from the array,
3. Repeat until the arrays are empty or the limit is reached.

The code to accomplish the above-outlined tasks might look something like this:

def merge_them(arrs)
  merged_array = []
  15.times do
    populated_arrays = []
    for i in 0..arrs.count - 1
      if arrs[i].count > 0
        populated_arrays.push(arrs[i])
      end
    end
    merged_array.push(find_winner(populated_arrays))
  end
  p merged_array
end
def find_winner(arrs)
  n = arrs.count
  max_arr = arrs.max_by { |arr| arr[0] }
  winner = max_arr[0]
  max_arr.shift
  winner
end

The merge_them function accepts multiple arrays. In this code, the limit is handled by the 15.times statement.

Only arrays that still have values will need to be searched. Those arrays are accumulated into the populated_arrays collection.

The find_winner method does the work of finding the array with the highest value, removing that value with the array shift method, and returning that value.

The returned value is pushed onto the merged_array.

Executing the merge_them function allows more control and is scalable over large-sized arrays and large numbers of arrays. And in try Ruby style, it only took a few lines of code.

Hopefully, this example helps to solve a similar problem for other developers. I’ll expand the logic here to work for more complex nested hashes, like what you’d expect from models utilized in a Ruby on Rails controller, in a future post.

Happy coding!