Merging Two Sorted Lists Into One In Descending Order

I've been able to figure out how to merge two sorted lists in ascending order, but I'm having trouble finding a way to do so in the opposite direction. How can I merge the two list

Solution 1:

You just have to do everything in the opposite way--retrieve items from the tail instead of the head, go for the larger of the two when making comparisons, and return the remaining list in reverse order when the other is exhausted:

def merge(lst1, lst2):
    if not lst1:
        return lst2[::-1]
    if not lst2:
        return lst1[::-1]
    if lst1[-1] < lst2[-1]:
        return [lst2[-1]] + merge(lst1, lst2[:-1])
    else:
        return [lst1[-1]] + merge(lst1[:-1], lst2)

so that:

 merge([2,5,9,12], [0,1,3,4,8])

would return:

 [12, 9, 8, 5, 4, 3, 2, 1, 0]