¿Por qué Java 6 Arrays # sort (Object ) cambia de mergesort a insertionsort para matrices pequeñas?

La implementación mergesort de Java 6 en Arrays.java usa una ordenación por inserción si la longitud del arreglo es menor que algún umbral. Este valor está codificado de forma rígida a 7. Como el algoritmo es recursivo, esto sucede muchas veces para una matriz grande. El algoritmo de combinación de orden canónico no hace esto, solo usa la ordenación de combinación hasta que solo haya 1 elemento en la lista.

¿Es esto una optimización? Si es así, ¿cómo se supone que debe ayudar? ¿Y por qué 7 ? La clasificación de inserción (incluso de <=7 cosas) aumenta el número de comparaciones necesarias para ordenar una gran variedad de forma espectacular, por lo que agregará un costo a una clasificación en la que las llamadas compareTo() son lentas.

tamaño de matriz vs # de comparaciones para diferentes valores de INSERTIONSORT_THRESHOLD

(el eje x es el size of array , el eje y es el # of comparisons , para diferentes valores de INSERTIONSORT_THRESHOLD )

Si esto es intencional Mientras que el Big-O de mergesort es menor que el de los géneros cuadráticos, como el ordenamiento de inserción, las operaciones que realiza son más complejas y, por lo tanto, más lentas.

Considere ordenar una matriz de longitud 8. La ordenación de fusión hace ~ 14 llamadas recursivas a sí misma además de 7 operaciones de combinación. Cada llamada recursiva contribuye con una sobrecarga no trivial al tiempo de ejecución. Cada operación de combinación involucra un bucle donde las variables de índice deben inicializarse, incrementarse y compararse, las matrices temporales deben copiarse, etc. En general, puede esperar más de 300 operaciones “simples”.

Por otro lado, la ordenación por inserción es intrínsecamente simple y utiliza aproximadamente 8 ^ 2 = 64 operaciones, lo que es mucho más rápido.

Piensa en ello de esta manera. Cuando ordena una lista de 10 números a mano, ¿utiliza ordenamiento por fusión? No, porque tu cerebro es mucho mejor para hacer cosas simples como ordenar por inserción. Sin embargo, si te diera un año para ordenar una lista de 100,000 números, podrías estar más inclinado a combinarla.

En cuanto al número mágico 7, se deriva empíricamente para ser óptimo.

EDITAR: En un tipo de inserción estándar de 8 elementos, el peor escenario conduce a ~ 36 comparaciones. En un tipo de combinación canónica, tiene ~ 24 comparaciones. Al agregar la sobrecarga de las llamadas al método y la complejidad de las operaciones, la ordenación por inserción debería ser más rápida. Además, si nos fijamos en el caso promedio, la ordenación por inserción haría muchas menos comparaciones que 36.

La clasificación de inserción es n (n-1) / 2 y la clasificación de fusión es n * (log n con base 2).

Considerando esto –

  1. Para Array of Length 5 => Inseeding sort = 10 y merge sort es 11.609
  2. Para una matriz de longitud 6 => Orden de inserción = 15 y la ordenación de combinación es 15.509
  3. Para Array of Length 7 => Insetion sort = 21 y merge sort es 19.651
  4. Para Array of Length 8 => Inseeding sort = 28 y merge sort es 24

De los datos anteriores está claro, hasta la longitud 6, el ordenamiento por inseminación es más rápido y después de 7, el tipo de fusión es eficiente.

Eso explica por qué se usa 7.

Tengo entendido que se trata de un valor derivado empíricamente, en el que el tiempo requerido para un tipo de inserción es en realidad más bajo, a pesar de que se requiere (posiblemente) un número mayor de comparaciones. Esto es así porque cerca del final de un mergesort, es probable que los datos estén casi ordenados , lo que hace que la ordenación por inserción tenga un buen rendimiento.