descending - sort array object java

¿Por qué Java 6 Arrays#sort(Object[]) cambia de mergesort a insertionsort para arreglos pequeños?

Question

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 gran matriz. El algoritmo canónico de ordenación por fusión no hace esto, solo usa la ordenación por fusión hasta que solo haya 1 elemento en la lista.

¿Es esta una optimización? Si es así, ¿cómo se supone que ayude? ¿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 manera espectacular, por lo que agregará un costo a una clasificación en la que las llamadas compareTo() son lentas.

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

Answer 1

Mi entendimiento es que este es un valor derivado empíricamente, donde el tiempo requerido para una clasificación de inserción es realmente menor, a pesar de un (posible) mayor número de comparaciones requeridas. Esto es así porque cerca del final de una combinación, es probable que los datos estén casi ordenados , lo que hace que la ordenación por inserción tenga un buen desempeño.

Answer 2

Sí, esto es intencional. Si bien el Big-O de mergesort es menor que el de ordenación cuadrática, como el tipo 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 implica 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 alrededor de 8 ^ 2 = 64 operaciones, que es mucho más rápida.

Piensa en ello de esta manera. Cuando ordena una lista de 10 números a mano, ¿utiliza ordenamiento por fusión? No, porque su cerebro es mucho mejor haciendo cosas simples como la ordenación 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 una inserción estándar de 8 elementos, el peor de los casos conduce a ~ 36 comparaciones. En una ordenación de fusión canónica, tienes ~ 24 comparaciones. Agregando 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 observa el caso promedio, la ordenación por inserción haría muchas menos comparaciones que 36.

Answer 3

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 una matriz de longitud 5 => Orden de inserción = 10 y la ordenación de combinación 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 el Array of Length 7 => Insetion sort = 21 y merge sort es 19.651
4. Para Array of Length 8 => Orden de inserción = 28 y la ordenación de combinación es 24

De los datos anteriores queda claro, hasta la longitud 6, la clasificación de inserción es más rápida y, después de 7, la clasificación de fusión es eficiente.

Eso explica por qué se usa 7.