In place merge.
Le acabo de dar algunas vueltas, y estoy casi seguro de que se puede hacer un merge con espacio adicional constante . Sean A y B los dos vectores a mezclar, la complejidad computaciotnal de dicho algoritmo sería siempre inferior a AxB.
El único problema que veo es que en el procesador iba a usar registros que te cagas, y que sería realmente complejo de programar, la búsqueda binaría incluiría a menudo elementos que no están en su posición original en el vector.