Friedrich Ewald My Personal Website

Merging two ordered lists efficiently in Python

To merge two lists l1, l2 in python, one can use the following

  1. Create two pointers, p1, p2
  2. Use a while loop, which is terminated, when one of the lists reaches the end
  3. Compare the entries of the list pairwise at the pointer position
    • If the entries are equal, add l1[p1] to result and increment p1 and p2 by 1
    • If l1[p1] < l2[p2], then add l1[p1] to result, then increment p1
    • If l1[p1] > l2[p2], then add l2[p2] to result, then increment p2
  4. 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]

About the author

is a Staff Software Engineer with a Master's degree in Computer Science. He started this website in late 2015, mostly as a digital business card. He is interested in Go, Python, Ruby, SQL- and NoSQL-databases, machine learning and AI and is experienced in building scalable, distributed systems and micro-services at multiple larger and smaller companies.

Related Posts