Merging two ordered lists efficiently in Python
28 Oct 2016 by Friedrich Ewald · 1 min readTo merge two lists l1
, l2
in python, one can use the following
- Create two pointers,
p1
,p2
- Use a while loop, which is terminated, when one of the lists reaches the end
- Compare the entries of the list pairwise at the pointer position
- If the entries are equal, add
l1[p1]
toresult
and incrementp1
andp2
by 1 - If
l1[p1] < l2[p2]
, then addl1[p1]
toresult
, then incrementp1
- If
l1[p1] > l2[p2]
, then addl2[p2]
toresult
, then incrementp2
- If the entries are equal, add
- Check, which list is not at the end and concat the tail of this list with
result
In Python code, this looks the following:
l1 = [1, 3, 5, 7, 9, 11]
l2 = [2, 4, 6]
p1 = 0
p2 = 0
result = []
# Loop over both lists until one list is at the end
while p1 < len(l1) and p2 < len(l2):
# If the values at the positions are the same,
# copy the value to the result
if l1[p1] == l2[p2]:
result.append(l1[p1])
result[-1] = l1[p1] + l2[p2]
p1 += 1
p2 += 1
# One entry is smaller, increment the smaller pointer
elif l1[p1] < l2[p2]:
result.append(l[p1])
p1 += 1
# One entry is smaller, increment the smaller pointer
elif l1[p1] > l2[p2]:
result.append(l2[p2])
p2 += 1
rest = []
if p1 < len(l1):
rest = l1[p1:len(l1)]
elif p2 < len(l2):
rest = list2[p2:len(l2)]
result += rest
# [1, 2, 4, 5, 6, 7, 9, 11]
I am Friedrich "Freddy" Ewald,
a software engineer from Germany, living in California. I started this blog in late 2015, mostly as a digital
business card when I bought this domain. Soon after, I started writing down observations and things that I learned
during my work or free time. I am deeply interested in all aspects around software, the internet and teamwork.
You can find more information about me on the about page.