Con respecto a la fusión in situ en una matriz

Me encontré con la siguiente pregunta.

Dada una matriz de n elementos y un número entero k donde k < n . Los elementos { a 0a k } y { a k +1a n } ya están clasificados. Proporcione un algoritmo para ordenar el tiempo O ( n ) y el espacio O (1).

No me parece que se pueda hacer en O ( n ) tiempo y O (1) espacio. El problema realmente parece ser preguntar cómo hacer el paso de fusión de mergesort, pero en el lugar. Si fuera posible, ¿no se implementaría mergesort de esa manera? Sin embargo, no puedo convencerme y necesito una opinión.

Esto parece indicar que es posible hacerlo en el espacio O (lg ^ 2 n). No veo cómo demostrar que es imposible fusionar en un espacio constante, pero tampoco puedo ver cómo hacerlo.

Editar: persiguiendo referencias, Knuth Vol 3 – Ejercicio 5.5.3 dice “Un algoritmo considerablemente más complicado de L. Trabb-Pardo proporciona la mejor respuesta posible a este problema: Es posible hacer una fusión estable en el tiempo O (n) y estable ordenando en O (n lg n) tiempo, usando solo O (lg n) bits de memoria auxiliar para un número fijo de variables de índice.

Más referencias que no he leído. Gracias por un problema interesante

Edición adicional: este artículo afirma que el artículo de Huang y Langston tiene un algoritmo que combina dos listas de tamaño myn en el tiempo O (m + n), por lo que la respuesta a su pregunta parece ser sí. Lamentablemente, no tengo acceso al artículo, por lo que debo confiar en la información de segunda mano. No estoy seguro de cómo conciliar esto con el pronunciamiento de Knuth de que el algoritmo de Trabb-Pardo es óptimo. Si mi vida dependiera de eso, iría con Knuth.

Ahora veo que esto se ha preguntado como y antes Pregunta de desbordamiento de stack varias veces. No tengo corazón para marcarlo como un duplicado.

Huang B.-C. y Langston MA, fusión práctica en el lugar, Comm. ACM 31 (1988) 348-352

Hay varios algoritmos para hacer esto, ninguno de los cuales es muy fácil de intuir. La idea clave es usar una parte de las matrices para fusionarlas como un búfer, luego hacer una fusión estándar usando este búfer para el espacio auxiliar. Si puede reposicionar los elementos para que los elementos del búfer estén en el lugar correcto, estará dorado.

He escrito una implementación de uno de estos algoritmos en mi sitio personal si está interesado en verlo. Se basa en el documento “Practical In-Place Merging” de Huang y Langston. Probablemente quieras revisar ese artículo para tener una idea.

También he escuchado que hay buenos algoritmos adaptativos para esto, que usan un búfer de tamaño fijo de su elección (que podría ser O (1) si lo desea), pero luego escala elegantemente con el tamaño del búfer. No conozco ninguno de estos en la parte superior de mi cabeza, pero estoy seguro de que una búsqueda rápida de “fusión adaptativa” podría generar algo.

No, no es posible, aunque mi trabajo sería mucho más fácil si fuera :).

Usted tiene un factor O (log n) que no puede evitar. Puede optar por tomarlo como tiempo o espacio, pero la única forma de evitarlo es no ordenar. Con el espacio O (log n) puede crear una lista de continuaciones que haga un seguimiento de dónde guardó los elementos que no encajaban. Con la recursión, se puede hacer que quepa en el montón O (1), pero eso es solo mediante el uso de marcos de stack O (log n).

Aquí está el progreso de las probabilidades y evences de clasificación por fusión del 1-9. Observe cómo requiere la contabilidad de espacio de registro para rastrear las inversiones de orden causadas por las restricciones gemelas de espacio constante y permutas lineales.

 .  -
 135792468
  .  -
 135792468
   :
 125793468
    :
 123795468
     #.: -
 123495768
      :
 123459768
       .: -
 123456798
        .-
 123456789

 123456789

Hay algunas condiciones de frontera delicadas, un poco más difíciles que la búsqueda binaria para hacer las cosas bien, e incluso en esta (posible) forma, y ​​por lo tanto un mal problema de tarea; pero un ejercicio mental realmente bueno.

Actualización Aparentemente estoy equivocado y hay un algoritmo que proporciona O (n) tiempo y O (1) espacio. He descargado los documentos para iluminarme y retiro esta respuesta como incorrecta.