Comparaciones
Escrituras
Mezclas

  • Parte en mezcla
  • Comparadas
  • Reescritas
  • Ya mezcladas

Más sobre el ordenamiento por mezcla

Ordenamiento por mezcla

El ordenamiento por mezcla es un algoritmo de divide y vencerás. Divide la lista por la mitad, ordena cada mitad de la misma forma y mezcla las dos mitades ordenadas tomando una y otra vez el menor de los primeros valores. Mira cómo las mitades pasan a una fila de búfer y vuelven en orden, a cualquier velocidad o paso a paso, y cuenta comparaciones, escrituras y mezclas. Pulsa Reproducir para ver la ordenación, o Paso y Atrás para avanzar paso a paso. Arrastra el control de pasos para saltar a cualquier punto. Los recuadros cuentan comparaciones, escrituras en la lista y mezclas. Elige cuántas barras hay, cómo empiezan, o escribe tus propios números. Con el tablero seleccionado, las flechas avanzan paso a paso, la barra espaciadora reproduce y pausa, e Inicio y Fin saltan al principio y al final.

Cómo funciona

  1. Elige cuántas barras hay y cómo empiezan: aleatorias, casi ordenadas, invertidas o con pocos valores distintos. O escribe tus propios números.
  2. Pulsa Reproducir, o usa Paso y Atrás para avanzar paso a paso. Arrastra el control de pasos para saltar a cualquier punto de la ordenación.
  3. Observa cada mezcla: las dos mitades ordenadas bajan al búfer, y el menor de los primeros valores vuelve a subir, de uno en uno.

Cómo funciona el ordenamiento por mezcla

Un solo valor ya está ordenado. Si la lista es más larga, divídela en dos mitades y ordena cada una con el ordenamiento por mezcla. Luego mézclalas: mira el primer valor de cada mitad, pasa el menor al resultado y repite hasta que las dos mitades estén vacías. Como las dos mitades están ordenadas, el resultado también lo está.

Siempre n log n

Dividir por la mitad una y otra vez da unos log₂ n niveles, y cada nivel de mezclas escribe cada valor una vez, así que la ordenación hace unas n log₂ n escrituras y como mucho otras tantas comparaciones. A diferencia del ordenamiento de burbuja, por selección y por inserción, eso no crece con n², y el orden de la lista importa mucho menos. El precio es un búfer tan largo como la lista. Además, el ordenamiento por mezcla es estable, y por eso es la base de las ordenaciones de Python y Java.

Preguntas frecuentes

¿Cómo funciona el ordenamiento por mezcla?

Divide la lista por la mitad, ordena cada mitad con el ordenamiento por mezcla y mezcla las dos mitades ordenadas tomando una y otra vez el menor de sus primeros valores. Una lista de un solo valor ya está ordenada, así que la división termina ahí.

¿Cuántas comparaciones hace el ordenamiento por mezcla?

Para n valores, como mucho unas n log₂ n − n + 1, y como mínimo cerca de la mitad de n log₂ n. Para 40 valores son como mucho 177. Las escrituras en la lista son siempre las mismas para un n dado: una por valor en cada nivel de mezcla.

¿Por qué el ordenamiento por mezcla necesita memoria extra?

Mezclar dos mitades sin salir de la lista es difícil de hacer rápido, así que la versión habitual copia las mitades en un búfer y las vuelve a escribir en orden. El búfer es tan largo como la lista, y esa es la principal desventaja frente a quicksort y heapsort.

¿Es estable el ordenamiento por mezcla?

Sí. Cuando los dos primeros valores son iguales, va primero el de la mitad izquierda, así que los valores iguales conservan su orden original.

¿Se envían mis números a algún sitio?

No. La ordenación se ejecuta en tu navegador, y tus últimos ajustes se guardan en el almacenamiento local de este navegador.

¿Listo para probarlo?

Abre PictorX en tu navegador: sin instalación ni tarjeta de crédito para empezar.

Ir al editor