Combining Two Sorted Lists in Python

Combining two sorted lists in Python

People seem to be over complicating this.. Just combine the two lists, then sort them:

>>> l1 = [1, 3, 4, 7]
>>> l2 = [0, 2, 5, 6, 8, 9]
>>> l1.extend(l2)
>>> sorted(l1)
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

..or shorter (and without modifying l1):

>>> sorted(l1 + l2)
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

..easy! Plus, it's using only two built-in functions, so assuming the lists are of a reasonable size, it should be quicker than implementing the sorting/merging in a loop. More importantly, the above is much less code, and very readable.

If your lists are large (over a few hundred thousand, I would guess), it may be quicker to use an alternative/custom sorting method, but there are likely other optimisations to be made first (e.g not storing millions of datetime objects)

Using the timeit.Timer().repeat() (which repeats the functions 1000000 times), I loosely benchmarked it against ghoseb's solution, and sorted(l1+l2) is substantially quicker:

merge_sorted_lists took..

[9.7439379692077637, 9.8844599723815918, 9.552299976348877]

sorted(l1+l2) took..

[2.860386848449707, 2.7589840888977051, 2.7682540416717529]

Merging two sorted python lists

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()).

How do I concatenate two lists in Python?

Use the + operator to combine the lists:

listone = [1, 2, 3]
listtwo = [4, 5, 6]

joinedlist = listone + listtwo

Output:

>>> joinedlist
[1, 2, 3, 4, 5, 6]

Efficient solution for merging 2 sorted lists in Python

Its because of the Python implementation of .sort(). Python uses something called Timsort.

Timsort is a type of mergesort. Its distinguishing characteristic is that it identifies "runs" of presorted data that it uses for the merge. In real world data, sorted runs in unsorted data are very common and you can sort two sorted arrays in O(n) time if they are presorted. This can cut down tremendously on sort times which typically run in O(nlog(n)) time.

So what's happening is that when you call list.sort() in Python, it identifies the two runs of sorted data list1 and list2 and merges them in O(n) time. Additionally, this implementation is compiled C code which will be faster than an interpreted Python implementation doing the same thing.

Merge two sorted lists and preserve order

You might want to use to use topological sorting. If you don't want to implement the algorithm from scratch, you can use the NetworkX Python package:

from itertools import chain
from networkx import DiGraph, topological_sort

l1 = ["A", "D", "B", "C"]
l2 = ["X", "A", "Y", "B"]

# Build the graph
G = DiGraph(chain(zip(l1[:-1], l1[1:]), zip(l2[:-1], l2[1:])))

# Return a list of nodes in topological sort order
result = list(topological_sort(G))

# result: ['X', 'A', 'Y', 'D', 'B', 'C']

Basically, you build a graph where every directed edge from vertex u to vertex v implies that u comes before v in the ordering. In this specific example, "A" comes before "D", "D" comes before "B" etc:

>>> G.edges
[('A', 'D'), ('A', 'Y'), ('D', 'B'), ('B', 'C'), ('X', 'A'), ('Y', 'B')]

Merging two sorted lists into a larger sorted list

Make sure you keep adding elements even if a list is out of elements. Your current code stops once either aList or bList is empty, which is probably not what you want.

You can do this by using the fact that an empty list is evaluated as False using an if expression:

def merge(aList, bList):
    newList = []
    while (aList or bList): # single empty list won't stop the loop
        if not bList or (aList and aList[0] < bList[0]):
            # either bList is empty, or aList has next item
            newList.append(aList.pop(0))
        else:
            # bList has next item
            newList.append(bList.pop(0))
    reutrn newList

list1 = [3, 4, 8, 9]
list2 = [1, 2, 5, 8]

print(merge(list1, list2))
print(list1)
print(list2)

Output:

sh-4.2# python3 main.py                                                                              
[1, 2, 3, 4, 5, 8, 8, 9]                                                                             
[]                                                                                                   
[]   

Merging two sorted lists into one in descending order

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]

---

Related Topics