Merging two sorted python lists

Question

I'm trying to merge two user inputted lists that have been sorted in descending order. I understand how to merge two lists then sort, however i'm struggling the other way around.

# user list input
a = [int(x) for x in input("List 1: ").split()]
b = [int(y) for y in input("List 2: ").split()]

a.sort(reverse=True)
b.sort(reverse=True)

print(a + b)

For example, I want to input: [1, 3, 3, 6] & [1, 4, 5], and my output be: [6, 5, 4, 3, 3, 1, 1]

Are you doing this because you *want a sorted list* or because you *want to learn to write a merge*? If you want a sorted list, just concatenate and sort. If you want to learn to write a merge, go read about mergesorts and look at how the merge step works. — user2357112, May 14 '21 at 03:55
If you're here to learn to write a merge, you're not going to learn much just from us dumping code on you. You'll have something to copy-paste, but copy-pasting doesn't help you understand how an algorithm works or help you learn to write your own code. — user2357112, May 14 '21 at 03:57
Yes im trying to write a merge. I understand how to combine the two then sort the lists. — , May 14 '21 at 04:00
Does this answer your question? [Combining two sorted lists in Python](https://stackoverflow.com/questions/464342/combining-two-sorted-lists-in-python). There's an implementation without using stdlib modules a few answers down. — SuperStormer, May 14 '21 at 04:30

score 1 · Answer 1 · answered May 14 '21 at 03:58

1

I suggest using sorted().

# user list input
a = [int(x) for x in input("List 1: ").split()]
b = [int(y) for y in input("List 2: ").split()]
print(sorted(a+b,reverse=True))

inp/out

List 1: 1 2 3 
List 2: 1 2 3
[3, 3, 2, 2, 1, 1]

answered May 14 '21 at 03:58

Buddy Bob

5,829
1
13
44

Thanks for the comment BuddyBob. However, i'm trying to merge the two inputs THEN sort them.. – May 14 '21 at 04:02
why? This seems to work perfectly fine? Anyways this does that just quicker. a+b merges them. sorted sorts the merged list. @patgoldgold – Buddy Bob May 14 '21 at 04:02
It's for a specific coding reason.. i know it's unnecessarily haha! – May 14 '21 at 04:06

score 1 · Accepted Answer · answered May 14 '21 at 04:27

You can use heapq.merge for this. It takes multiple sorted iterables and merges them into a single sorted output, so:

c = list(heapq.merge(
    sorted(a, reverse=True),
    sorted(b, reverse=True),
    reverse=True)

Note that this works also with iterables (e.g. lazily-calculated, potentially consumable objects), which is when you are more likely to use it (when combining sorted iterables).

I am assuming you get the lists pre-sorted or you just want to know how to do this, since it would probably be preferable to merge the lists first and then sort them (either with sorted or mutating them with .sort()).

Merging two sorted python lists

2 Answers2