¿Por qué Collections.sort usa Mergesort pero Arrays.sort no?

Estoy usando JDK-8 (x64). Para Arrays.sort (primitives) encontré lo siguiente en la documentación de Java:

El algoritmo de clasificación es un Quicksort Dual-Pivot de Vladimir Yaroslavskiy, Jon Bentley y Joshua Bloch.

Para Collections.sort (objetos) encontré este “Timsort”:

Esta implementación es una combinación de procesos iterativa estable, adaptable e iterativa … Esta implementación vuelca la lista especificada en una matriz, ordena la matriz y repite la lista restableciendo cada elemento desde la posición correspondiente en la matriz.

Si Collections.sort usa una matriz, ¿por qué no solo llama a Arrays.sort o utiliza QuickSort de doble pivote? ¿Por qué usar Mergesort ?

    La API garantiza una clasificación estable que Quicksort no ofrece. Sin embargo, al ordenar valores primitivos por su orden natural, no notará una diferencia ya que los valores primitivos no tienen identidad. Por lo tanto, Quicksort se usa para matrices primitivas ya que es ligeramente más eficiente.

    Para objetos que puede observar, cuando los objetos que se consideran iguales de acuerdo con su implementación equals o el Comparator provisto cambian su orden. Por lo tanto, Quicksort no es una opción. Entonces se usa una variante de MergeSort, las versiones actuales de Java usan TimSort . Esto se aplica tanto a Arrays.sort como a Collections.sort , aunque con Java 8, la List sí misma puede anular los algoritmos de ordenación.

    No sé sobre la documentación, pero la implementación de java.util.Collections#sort en Java 8 (HotSpot) es la siguiente:

     @SuppressWarnings({"unchecked", "rawtypes"}) public static  void sort(List list, Comparator< ? super T> c) { list.sort(c); } 

    Y List#sort tiene esta implementación:

     @SuppressWarnings({"unchecked", "rawtypes"}) default void sort(Comparator< ? super E> c) { Object[] a = this.toArray(); Arrays.sort(a, (Comparator) c); ListIterator i = this.listIterator(); for (Object e : a) { i.next(); i.set((E) e); } } 

    Entonces, al final, Collections#sort usa Arrays#sort (de elementos de objeto) detrás de las escenas. Esta implementación usa tipo de fusión o clasificación por tiempo.

    Según Javadoc, solo las matrices primitivas se ordenan usando Quicksort. Las matrices de objetos también se ordenan con un Mergesort.

    Así que Collections.sort parece usar el mismo algoritmo de clasificación que Arrays.sort para Objects.

    Otra pregunta sería ¿por qué se usa un algoritmo de clasificación diferente para las matrices primitivas que para las matrices de Objetos?

    Como se indica en muchas de las respuestas.

    QuickSort es utilizado por Arrays.sort para clasificar recolecciones primitivas porque no se requiere estabilidad (no se sabrá ni se importará si se intercambiaron dos identidades idénticas en el orden)

    MergeSort o más específicamente Timsort es utilizado por Arrays.sort para ordenar colecciones de objetos. Estabilidad es requerida. Quicksort no proporciona estabilidad, Timsort lo hace.

    Collections.sort delega en Arrays.sort y es por eso que ve el javadoc haciendo referencia a MergeSort.

    Quick Sort tiene dos inconvenientes principales cuando se trata de merge sort:

    • No es estable mientras no sea primitivo.
    • No garantiza el rendimiento n log n.

    La estabilidad no es un problema para los tipos primitivos, ya que no existe la noción de identidad como distinta de la igualdad (de valor).

    La estabilidad es un gran problema cuando se ordenan objetos arbitrarios. Es un buen beneficio lateral que Merge Sort garantice n log n (tiempo) de rendimiento sin importar la entrada. Es por eso que el tipo de combinación se selecciona para proporcionar un tipo estable (Clasificación de combinación) para ordenar referencias de objetos.