Algoritmos: apareo de listas ordenadas sin modificar las listas originarias

Un problema típico de entrevista es ordenar dos listas con elementos ya ordenados previamente. La idea es tener en cuenta que ya estan ordenados y no reordenar (que sería el peor camino). Para esto voy adicionando los elementos más pequeños y luego extender si quedo un subconjunto por fuera del "comparado" en las iteraciones del while. Bueno aquí va el algoritmo.

def merge_sorted_arrays(a, b):
    len_a = len(a)
    len_b = len(b)

    pos_a = 0
    pos_b = 0

    merged_list = []
    while pos_a < len_a and pos_b < len_b:
        if a[pos_a] <= b[pos_b]:
            merged_list.append(a[pos_a])
            pos_a += 1
        else:
            merged_list.append(b[pos_b])
            pos_b += 1

    if pos_a < len_a:
        merged_list.extend(a[pos_a:])
    if pos_b < len_b:
        merged_list.extend(b[pos_b:])

    return merged_list

a = [1, 2, 3, 4]
b = [3, 3, 8, 9]
expected = [1, 2, 3, 3, 3, 4, 8, 9]


result = merge_sorted_arrays(a, b)
print(expected == result)
Copy

No es gran cosa, simplemente uso una 3ra lista para ir guardando los elementos. Y luego extenderal segun la lista que se haya quedado sin recorrer o sea con los elementos de numeros más grandes (y ordenados).