Que el orden sea O(2n + 2m) no es problema porque es lo mismo que O(n+m).
El problema es que, si le estás dando el significado correcto a concatenar, el resultado no es correcto. La lista no quedaría ordenada, y además quedarían repetidos los elementos que están en ambas listas, los cuales deberían quedar solo una vez, y además quedarían los elementos que están solo en una de las listas, los cuales no deberían quedar.
El problema es que, si le estás dando el significado correcto a concatenar, el resultado no es correcto. La lista no quedaría ordenada, y además quedarían repetidos los elementos que están en ambas listas, los cuales deberían quedar solo una vez, y además quedarían los elementos que están solo en una de las listas, los cuales no deberían quedar.
En el ejemplo de la letra te quedaría la lista [8,4,3,1,9.8.7.6.4.2,1 ].