Sé que el método Arrays.sort de Java usa MergeSort para clasificar matrices de objetos (o colecciones de objetos) ya que es estable, y Java usa QuickSort para matrices de primitivas porque no necesitamos estabilidad ya que dos enteros iguales son indistinguibles, es decir, su la identidad no importa.
Mi pregunta es, en el caso de las primitivas, ¿por qué Java no usa el tiempo O (n log n) garantizado de MergeSort y en su lugar busca el tiempo promedio O (n log n) de QuickSort? En el último párrafo de una de las respuestas relacionadas aquí , se explica que:
Para los tipos de referencia, donde los objetos a los que se hace referencia suelen ocupar mucha más memoria que la matriz de referencias, esto generalmente no importa. Pero para los tipos primitivos, la clonación de la matriz duplica el uso de la memoria.
¿Qué significa esto? La clonación de una referencia sigue siendo al menos tan costosa como la clonación de una primitiva. ¿Hay alguna otra razón para usar QuickSort (promedio O (n log n)) en lugar de MergeSort (garantizado O (n log n) time) en matrices de primitivas?
No todos los algoritmos O(n log n) tienen los mismos factores constantes. Quicksort, en el 99,9 % de los casos en los que tarda n log n tiempo, se ejecuta en un n log n mucho más rápido que mergesort. No conozco el multiplicador exacto, y variará de un sistema a otro, pero, digamos, la ordenación rápida podría ejecutarse dos veces más rápido que la ordenación por fusión en promedio y aún así tener un rendimiento teórico en el peor de los casos n^2.
Además, Quicksort no requiere clonar la matriz en primer lugar, y la ordenación por combinación inevitablemente lo hace. Pero no tiene opción para los tipos de referencia si desea una clasificación estable, por lo que debe aceptar la copia, pero no necesita aceptar ese costo para las primitivas.
La clonación de una referencia sigue siendo al menos tan costosa como la clonación de una primitiva.
La mayoría (¿o todas?) de las implementaciones de Java implementan una matriz de objetos como una matriz de punteros (referencias) a objetos. Por lo tanto, clonar una matriz de punteros (referencias) consumiría menos espacio que clonar los propios objetos si los objetos tienen un tamaño mayor que un puntero (referencia).
No sé por qué se usó el término "clonación". La ordenación por combinación asigna una segunda matriz temporal, pero la matriz no es un "clon" del original. En cambio, una clasificación de combinación adecuada alterna la dirección de combinación de original a temporal o de temporal a original según la iteración de abajo hacia arriba, o según el nivel de recursividad de arriba hacia abajo.
clasificación rápida de doble pivote
Según lo que puedo encontrar al hacer búsquedas en la web, la ordenación rápida de doble pivote de Java realiza un seguimiento de las "recursiones" y cambia a la ordenación en montón si la profundidad de la recursión es excesiva, para mantener la complejidad del tiempo O (n log (n)), pero a un nivel más alto. factor de costo
ordenación rápida versus ordenación por fusión
Además de la estabilidad, la ordenación por combinación puede ser más rápida para ordenar una matriz de punteros (referencias) a objetos. La ordenación por combinación hace más movimientos (de los punteros) pero menos comparaciones (de los objetos a los que se accede mediante punteros de desreferenciación) que la ordenación rápida.
En un sistema con 16 registros (la mayoría de ellos se usan como punteros), como X86 en modo de 64 bits, una clasificación de combinación de 4 vías es casi tan rápida como la clasificación rápida normal, pero no recuerdo haber visto una combinación de 4 vías ordenar en una biblioteca común, al menos no para una PC.
Arrays#sort(primitive array) no usa la ordenación rápida tradicional; utiliza Dual-Pivot Quicksort, que es más rápido que quicksort, que a su vez es más rápido que merge sort, en parte porque no tiene que ser estable.
Del javadoc:
Nota de implementación: el algoritmo de clasificación es un Quicksort de doble pivote de Vladimir Yaroslavskiy, Jon Bentley y Joshua Bloch. Este algoritmo ofrece un rendimiento O(n log(n)) en muchos conjuntos de datos que hacen que otras clasificaciones rápidas se degraden a un rendimiento cuadrático y, por lo general, es más rápido que las implementaciones tradicionales de clasificación rápida (un pivote).