Algoritmo

Datos: dos listas ordenadas [1, 2,6, 8, 9] y [3, 4, 5, 7]

Cmo intercalar los numeros de una y otra lista para tener una unica lista ordenada?

Comenzamos tratando de ubicar el 3 en la primera lista, por ejemplo.

Comparamos el 3 con 1 y decidimos que es mas grande, y hacemos lo mismo con el 2.

Pero vemos que es menor que 6.

Asi que la lista intercalada empezara por la serie [1, 2, 3, ...] y observamos que este trozo lo hemos obtenido con solo tantas operaciones como el puesto que ocupa el numero 3 en la nueva lista.

Seguimos con el numero 4, y, como la lista [3, 4, 5, 7] ya viene ordenada, solo lo necesitamos comparar con los vertices siguientes a 3, en la lista parcial, es decir 6, 8, 9, concluyendo que la lista va a continuar como [1, 2, 3, 4, 6,...].

Notese que hemos hecho, en total 3+1 comparaciones, tantas como el puesto que ocupa en la lista el ultimo numero que hemos intercalado, el 4.

Cogemos ahora el numero 5, y vemos que es menor que el 6 . Lo incluimos en la lista, tras 3+1+1 comparaciones,
queda [1, 2, 3, 4, 5, 6, 8, 9].

Idem, con el 7, comparamos con 8, es menor. En total, han sido 3+1+1+1 comparaciones.

En resumen, si las listas dadas son de menos de M numeros, la mezcla ordenada nos llevara, tambien, menos de M pasos.