Merging two ordered lists efficiently in Python
To 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
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]