Merge two sorted lists in Python (two pointers)

Both lists are already sorted, so the smallest remaining item is always at the front of one of them. Compare the two front items, take the smaller one, and move forward in that list. Repeat until one list is used up.

The program

python

def merge_sorted(a, b):
    result = []
    i = j = 0
    while i < len(a) and j < len(b):
        if a[i] <= b[j]:
            result.append(a[i])
            i += 1
        else:
            result.append(b[j])
            j += 1
    result.extend(a[i:])               # at most one of these two adds anything
    result.extend(b[j:])
    return result

print(merge_sorted([1, 4, 9, 12], [2, 3, 10]))
print(merge_sorted([5, 8], []))
print(merge_sorted([2, 2, 7], [2, 5]))

output

[1, 2, 3, 4, 9, 10, 12]
[5, 8]
[2, 2, 2, 5, 7]

How it works

i and j are two pointers: the position of the next unused item in a and in b.
Each step adds one item to result and moves one pointer forward. So the loop runs at most len(a) + len(b) times, and the lists are never sorted again.
When one list is used up, the rest of the other list is already sorted and bigger than everything taken so far, so extend() adds it all at the end.
An empty list works: the while loop does not run, and extend() copies the other list.
Neither input list is changed.

This merge is the second half of merge sort.

Another way: heapq.merge() and sorted()

python

import heapq

a = [1, 4, 9, 12]
b = [2, 3, 10]
c = [0, 11]

print(list(heapq.merge(a, b)))
print(list(heapq.merge(a, b, c)))
print(sorted(a + b))

output

[1, 2, 3, 4, 9, 10, 12]
[0, 1, 2, 3, 4, 9, 10, 11, 12]
[1, 2, 3, 4, 9, 10, 12]

heapq.merge() merges any number of sorted lists. It returns an iterator that gives one item at a time, so list() is needed to see them all. Because it works one item at a time, it can also merge very large sorted files without loading them fully into memory.
sorted(a + b) is the shortest way, and it also works when the lists are not sorted. Python's sort notices that a + b is made of two sorted parts, so it is fast here too.