Сначала попробуйте сами: на собеседовании подсказки не будет.
Классическое слияние из merge sort: два указателя, на каждом шаге берём меньший из текущих элементов и сдвигаем его указатель. Когда один список кончился, остаток другого дописываем целиком через extend, он уже отсортирован.
a[i] <= b[j] с нестрогим сравнением сохраняет устойчивость: при равных элементах первым идёт элемент из a. heapq.merge(a, b) делает то же самое лениво.
def merge_sorted(a, b):
i = j = 0
out = []
while i < len(a) and j < len(b):
if a[i] <= b[j]:
out.append(a[i])
i += 1
else:
out.append(b[j])
j += 1
out.extend(a[i:])
out.extend(b[j:])
return out