Ejemplo Mergesort 01

L1 = 4, 15, 16, 50   L2 = 8, 23, 42, 108    L3 = (empty)

Comparamos 4 con 8. 4 es menor, concatenamos a L3 y removemos de L1.

L1 = 15, 16, 50      L2 = 8, 23, 42, 108    L3 = 4

Comparamos 15 con 8. 8 es menor, concatenamos a L3 y removemos de L2.

L1 = 15, 16, 50      L2 = 23, 42, 108       L3 = 4, 8

Comparamos 15 con 23. 15 es menor, concatenamos a L3 y removemos de L1.

L1 = 16, 50          L2 = 23, 42, 108       L3 = 4, 8, 15

Comparamos 16 con 23. 16 es menor, concatenamos a L3 y removemos de L1.

L1 = 50              L2 = 23, 42, 108       L3 = 4, 8, 15, 16

Comparamos 50 con 23. 23 es menor, concatenamos a L3 y removemos de L2.

L1 = 50              L2 = 42, 108           L3 = 4, 8, 15, 16, 23

Comparamos 50 con 42. 42 es menor, concatenamos a L3 y removemos de L2.

L1 = 50              L2 = 108               L3 = 4, 8, 15, 16, 23, 42

Comparamos 50 con 108. 50 es menor, concatenamos a L3 y removemos de L1.

L1 =                 L2 = 108               L3 = 4, 8, 15, 16, 23, 42, 50

Como L1 se vació solo tenemos que copiar el resto de los elementos de L2 al final de L3.
El resultado final es L3.

L1 =                 L2 =                   L3 = 4, 8, 15, 16, 23, 42, 50, 108

Para hacer merge esas dos listas hicimos 7 comparaciones entre los elementos de las dos listas. La cantidad de comparaciones crece linealmente con el número total de elementos en las listas, i.e. el número de comparaciones es O(n) donde n es la cantidad total de elementos de L1 y L2.