Ordenar un array con la primera mitad y la segunda mitad ordenadas

Question

Duplicar posible:
Regarding in-place merge in an array

Tropezamos con esta pregunta de la entrevista. Dada una matriz de tamaño n donde se ordenan los primeros n/2 y se ordena la segunda mitad . Clasifica toda la matriz en su lugar. Ahora, lo que puedo pensar en su lugar es algo así como tipo de inserción, que tendrá complejidad de espacio como O (1), pero la complejidad del tiempo será mayor que O (n). ¿Existe una solución O (n) en su lugar para este problema?

Answer 1

Tiene dos punteros (lógicos) - vamos a llamarlos x e y. x apunta al primer elemento de los primeros n/2 elementos. y apunta al primer elemento de los segundos n/2 elementos.

Si el elemento en Y es menor que el de x (vamos a llamar a n (y) y n (x)), a continuación, insertar n (y) en x y el incremento x & y por 1. incremento Else x por 1 y revisa nuevamente Una vez que golpee 'n', pare y siga repitiendo hasta x == y.

E.g.

2 4 7 8 1 3 5 6 
x  y 

1 2 4 7 8 3 5 6 
    x  y 

1 2 4 7 8 3 5 6 
    x  y 

1 2 3 4 7 8 5 6 
     x  y 

1 2 3 4 7 8 5 6 
     x y 

1 2 3 4 5 7 8 6 
      x y 

1 2 3 4 5 6 7 8 
      x y 

1 2 3 4 5 6 7 8 
       (x,y) 

Answer 2

Normalmente, para ordenar dos listas ya ordenadas, utilizaría la clase de fusión; la forma más simple sería copiar una de las medias matrices en alguna parte. Eso no está en su lugar, pero funciona.

Intercambio de elementos no funciona, ya que no garantiza el valor máximo de la primera mitad de la matriz es menor que el valor mínimo en la mitad derecha:

{ 3 4 4 1 2 4 } 

intercambio i = 0, j = 3

{ 1 4 4 3 2 4 } 

intercambio i = 1, j = 5

{ 1 2 4 3 4 4 } 

la fijación de este mediante el canje aún más los resultados en una O (N^2) tipo de burbuja.