Best way to concatenate two sorted integer lists

Question

Suppose I have one list and another tuple, both of them are already sorted:

A = [10, 20, 30, 40] B = (20, 60, 81, 90) 

I will need to add all the elements from B to such that A remains sorted.

The solution I could come with was:

 for item in B: for i in range(0, len(A)): if item > A[i]: i += 1 else: A.insert(i, item) 

assuming A of size m and B of size n; this decision will be made by O (m x n) in the worst case, how can I make it work better?

Answer 1

A simple way would be heapq.merge :

 A = [10, 20, 30, 40] B = (20, 60, 81, 90) from heapq import merge for ele in merge(A,B): print(ele) 

Output:

 10 20 20 30 40 60 81 90 

Some timings using another O(n) solution:

 In [53]: A = list(range(10000)) In [54]: B = list(range(1,20000,10)) In [55]: timeit list(merge(A,B)) 100 loops, best of 3: 2.52 ms per loop In [56]: %%timeit C = [] i = j = 0 while i < len(A) and j < len(B): if A[i] < B[j]: C.append(A[i]) i += 1 else: C.append(B[j]) j += 1 C += A[i:] + B[j:] ....: 100 loops, best of 3: 4.29 ms per loop In [58]: m =list(merge(A,B)) In [59]: m == C Out[59]: True 

If you want to make your own, this is slightly faster than merging:

 def merger_try(a, b): if not a or not b: yield chain(a, b) iter_a, iter_b = iter(a), iter(b) prev_a, prev_b = next(iter_a), next(iter_b) while True: if prev_a >= prev_b: yield prev_b try: prev_b = next(iter_b) except StopIteration: yield prev_a break else: yield prev_a try: prev_a = next(iter_a) except StopIteration: yield prev_b break for ele in chain(iter_b, iter_a): yield ele 

Some timings:

 In [128]: timeit list(merge(A,B)) 1 loops, best of 3: 771 ms per loop In [129]: timeit list(merger_try(A,B)) 1 loops, best of 3: 581 ms per loop In [130]: list(merger_try(A,B)) == list(merge(A,B)) Out[130]: True In [131]: %%timeit C = [] i = j = 0 while i < len(A) and j < len(B): if A[i] < B[j]: C.append(A[i]) i += 1 else: C.append(B[j]) j += 1 C += A[i:] + B[j:] .....: 1 loops, best of 3: 919 ms per loop 

Answer 2

bisect module "provides support for maintaining a list in sorted order without sorting the list after each insertion":

 import bisect for b in B: bisect.insort(A, b) 

This solution does not create a new list.

---

Note that bisect.insort(A, b) equivalent

 A.insert(bisect.bisect_right(A, b), b) 

Even if the search is fast (O (log n)), the insert is slow ( O (n) ).

Answer 3

Lots of good discussion in this post! Talking about timing is hard, so I wrote a few temporary scripts. This is pretty rudimentary, but I think it will be done now. I also attached the results.

 import timeit import math import matplotlib.pyplot as plt from collections import defaultdict setup = """ import bisect import heapq from random import randint A = sorted((randint(1, 10000) for _ in range({}))) B = sorted((randint(1, 10000) for _ in range({}))) def bisect_sol(A, B): for b in B: bisect.insort(A, b) def merge_sol(A, B): ia = ib = 0 while ib < len(B): if ia < len(A) and A[ia] < B[ib]: if ia < len(A): ia += 1 else: A.insert(ia + 1, B[ib]) ib += 1 def heap_sol(A, B): return heapq.merge(A, B) def sorted_sol(A, B): return sorted(A + B) """ sols = ["bisect", "merge", "heap", "sorted"] times = defaultdict(list) iters = [100, 1000, 2000, 5000, 10000, 20000, 50000, 100000] for n in iters: for sol in sols: t = min(timeit.repeat(stmt="{}_sol(A, B)".format(sol), setup=setup.format(n, n), number=1, repeat=5)) print("({}, {}) done".format(n, sol)) times[sol].append(math.log(t)) for sol in sols: plt.plot(iters, times[sol]) plt.xlabel("iterations") plt.ylabel("log time") plt.legend(sols) plt.show() 

This is the result:

Clearly changing the list is the main bottleneck, so creating a new list is the way to go.

Answer 4

Here is the solution in O(n) :

 A = [10, 20, 30, 40] B = [20, 60, 81, 90] C = [] i = j = 0 while i < len(A) and j < len(B): if A[i] < B[j]: C.append(A[i]) i += 1 else: C.append(B[j]) j += 1 C += A[i:] + B[j:] 

Answer 5

edited

 l1 = [10,20,30,40] l2 = (10,20,30,40) l2 = list(l2) l1 = sorted(l1+l2) 

Answer 6

You need to perform a merge. But the “traditional” merge generates a new list; so you need to make some changes to expand one list.

 ia = ib = 0 while ib < len(B): if ia < len(A) and A[ia] < B[ib]: if ia < len(A): ia += 1 else: A.insert(ia + 1, B[ib]) ib += 1