Combining two sorted lists in Python
This is simply merging. Treat each list as if it were a stack, and continuously pop the smaller of the two stack heads, adding the item to the result list, until one of the stacks is empty. Then add all remaining items to the resulting list.
res = []
while l1 and l2:
if l1[0] < l2[0]:
res.append(l1.pop(0))
else:
res.append(l2.pop(0))
res += l1
res += l2
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]
is there a smarter way to do this in Python
This hasn't been mentioned, so I'll go ahead - there is a merge stdlib function in the heapq module of python 2.6+. If all you're looking to do is getting things done, this might be a better idea. Of course, if you want to implement your own, the merge of merge-sort is the way to go.
>>> list1 = [1, 5, 8, 10, 50]
>>> list2 = [3, 4, 29, 41, 45, 49]
>>> from heapq import merge
>>> list(merge(list1, list2))
[1, 3, 4, 5, 8, 10, 29, 41, 45, 49, 50]
Here's the documentation.
Long story short, unless len(l1 + l2) ~ 1000000
use:
L = l1 + l2
L.sort()
Description of the figure and source code can be found here.
The figure was generated by the following command:
$ python make-figures.py --nsublists 2 --maxn=0x100000 -s merge_funcs.merge_26 -s merge_funcs.sort_builtin