Built-in method for combining two sorted lists in ruby

Question

I have two lists of Foo objects. Each Foo object has a timestamp, Foo.timestamp. Both lists are first sorted by timestamp in descending order.

I want to combine both lists of Foo objects so that the final list is also sorted by timestamps in descending order.

Implementing this is not difficult, but I was wondering if there are any built-in Ruby methods that can do this, since I believe that the built-in methods will bring better performance.

Thanks.

Answer 1

This will work, but it will not give much performance, because it will not use a list already sorted in advance:

list = (list1 + list2).sort_by(&:timestamp) 

I do not know any built-in function that does what you want.

Answer 2

I quickly looked at Array#sort and Enumerable#sort , and both seem to be using quicksort . Thus, they may not be as effective as you are manually using a merge sort that selects which of the two potential items will be displayed in the new list one at a time.

However, a good article on self-destructive sorting algorithms shows that one of those trying to do better than the basic quicksort failed - it did not directly approach the problem you have, but its numbers are pretty dull, and I will try default sorting first Enumerable#sort_by , and only if it feels too slow will I return to trying to create a self-contained merge record.

Answer 3

The impressive imperative process of merging the two ...

 a = [1,3,7,11] b = [2,4,6,14] c = merge_sorted_arrays(a,b) def merge_sorted_arrays(a,b) a.reverse! b.reverse! output = [] loop do break if a.empty? || b.empty? output << (a.last < b.last ? a.pop : b.pop) end return output + a.reverse + b.reverse end 

Perhaps the use of .slice! taking the first element is better than reversing and popping up?

======================

edited after the fourth comment:

That's right ... I had a different game, but I need to do real work or they will fire me; -)

In a large array of integers, my original method is faster than using sort_by, but after filling in the arrays of 100,000 OpenStruct objects and sorting by the sort_by attribute, it was 100 times faster.

Here are my benchmarking results:

 def pop_merge_sorted_arrays(array1,array2) array1.reverse! array2.reverse! output = [] loop do break if array1.empty? || array2.empty? output << (array1.last.my_field < array2.last.my_field ? array1.pop : array2.pop) end return output + array1.reverse + array2.reverse end def shift_merge_sorted_arrays(array1,array2) output = [] loop do break if array1.empty? || array2.empty? output << (array1.first.my_field < array2.first.my_field ? array1.shift : array2.shift) end return output + array1 + array2 end def slice_merge_sorted_arrays(array1,array2) output = [] loop do break if array1.empty? || array2.empty? output << (array1.first.my_field < array2.first.my_field ? array1.slice!(0) : array2.slice!(0)) end return output + array1 + array2 end a=(1..100000).map{|x|OpenStruct.new(:my_field => rand)}.sort_by(:my_field) b=(1..100000).map{|x|OpenStruct.new(:my_field => rand)}.sort_by(:my_field) # method 1 t=Time.now;w=pop_merge_sorted_arrays(a.clone,b.clone);puts Time.now-t # average of five runs: 185.96seconds # method 2 t=Time.now;x=shift_merge_sorted_arrays(a.clone,b.clone);puts Time.now-t # average of five runs: 0.77seconds # method 3 t=Time.now;y=slice_merge_sorted_arrays(a.clone,b.clone);puts Time.now-t # average of five runs: 8.46seconds # method 4 t=Time.now;z=(a.clone + b.clone).sort_by(&:my_field);puts Time.now-t # average of five runs: 2.13seconds 

Thus, it seems that you can write a method that will shuffle them, while preserving the order, which will be pretty fast (and there are probably a few more advantages to squeezing the shift_merge method, but it really doesn’t have to be worth it just combine them together and use sort_by for convenience? :-)

I hope this is not considered a retreat ...