CODEWITHSUNDEEP
pythonrecursionmerge
John Wahlberg
John Wahlberg

Reputation: 31

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 lists into one in descending order without reversing the string after?

Upvotes: 3

Views: 1289

Answers (1)

blhsing
blhsing

Reputation: 106512

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]

Upvotes: 1

Related Questions