built in method to merge two sorted lists in ruby

Question

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

I want to merge both the lists of Foo objects in a way where the final list is also sorted by timestamp in descending order.

Implementing this isn't hard, but I was wondering whether there are there any built-in Ruby methods that can do this, as I assume the built-in methods will yield the best performance.

Thanks.

Answer 1

This will work, but it will not give great performance because it won't take advantage of the lists already being sorted beforehand:

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

I don't know of any built-in function that does what you want.

Answer 2

I took a quick look at the Array#sort and Enumerable#sort implementations and both appear to use quicksort. Thus, they might not be as efficient as you manually using a merge sort that selects which of the two potential elements to output to the new list in turn.

However, a nice article about self-implemented sorting algorithms shows that one programmer's efforts to do better than the underlying quicksort failed miserably -- he did not directly approach the problem you have, but his numbers are daunting enough that I'd try the default Enumerable#sort_by sorting first, and only if it feels too slow would I return to trying a self-written merge sort.