Pourquoi Collections.sort utilise Mergesort mais pas Arrays.sort?

J'utilise JDK-8 (x64). Pour Arrays.sort(primitives), j'ai trouvé ce qui suit dans la documentation Java:

L'algorithme de tri est un double-pivot Quicksort par Vladimir Yaroslavskiy, Jon Bentley, et Joshua Bloch.`

Pour Collections.sort(objets) j'ai trouvé ce "Timsort":

Cette implémentation est un mergesort stable, adaptatif et itératif ... Cette implémentation vide la liste spécifiée dans un tableau, trie le tableau et itère sur la liste en réinitialisant chaque élément à partir de la position correspondante dans le tableau.

Si Collections.sortutilise un tableau, pourquoi n'appelle-t-il pas Arrays.sortou n'utilise- t-il pas simplement QuickSort à double pivot ? Pourquoi utiliser Mergesort ?

L'API garantit un tri stable que Quicksort n'offre pas. Cependant, lors du tri des valeurs primitives selon leur ordre naturel, vous ne remarquerez aucune différence car les valeurs primitives n'ont pas d'identité. Par conséquent, Quicksort peut être utilisé pour les tableaux primitifs et sera utilisé lorsqu'il sera considéré comme plus efficace¹.

Pour les objets, vous remarquerez peut-être, lorsque des objets avec une identité différente qui sont jugés égaux en fonction de leur equalsimplémentation ou du fourni Comparatorchangent leur ordre. Par conséquent, Quicksort n'est pas une option. Donc, une variante de MergeSort est utilisée, les versions Java actuelles utilisent TimSort . Cela s'applique aux deux Arrays.sortet Collections.sort, bien qu'avec Java 8, le Listlui-même peut remplacer les algorithmes de tri.

¹ L'avantage d'efficacité de Quicksort est qu'il nécessite moins de mémoire lorsqu'il est effectué sur place. Mais il a des performances dramatiques dans le pire des cas et ne peut pas exploiter des séries de données pré-triées dans un tableau, ce que fait TimSort .

Par conséquent, les algorithmes de tri ont été retravaillés de version en version, tout en restant dans la classe désormais mal nommée DualPivotQuicksort. De plus, la documentation n'a pas rattrapé son retard, ce qui montre que c'est une mauvaise idée en général de nommer un algorithme utilisé en interne dans une spécification, quand ce n'est pas nécessaire.

La situation actuelle (y compris Java 8 à Java 11) est la suivante:

• En règle générale, les méthodes de tri des tableaux primitifs n'utilisent Quicksort que dans certaines circonstances. Pour les tableaux plus grands, ils essaieront d'abord d'identifier les séries de données pré-triées, comme le fait TimSort , et les fusionneront lorsque le nombre d'exécutions ne dépasse pas un certain seuil. Sinon, ils reviendront à Quicksort , mais avec une implémentation qui reviendra au tri par insertion pour les petites plages, ce qui n'affecte pas seulement les petits tableaux, mais également la récursivité du tri rapide.
• sort(char[],…)et sort(short[],…)ajoutez un autre cas particulier, pour utiliser le tri par comptage pour les tableaux dont la longueur dépasse un certain seuil
• De même, sort(byte[],…)utilisera le tri par comptage , mais avec un seuil beaucoup plus petit, ce qui crée le plus grand contraste avec la documentation, car il sort(byte[],…)n'utilise jamais Quicksort. Il utilise uniquement le tri par insertion pour les petits tableaux et le tri par comptage dans le cas contraire.

Je ne connais pas la documentation, mais l'implémentation de java.util.Collections#sortJava 8 (HotSpot) se déroule comme suit:

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

Et List#sorta cette implémentation:

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

Donc, à la fin, Collections#sortutilise Arrays#sort(des éléments d'objet) dans les coulisses. Cette implémentation utilise le tri par fusion ou le tri par tim.

Selon Javadoc, seuls les tableaux primitifs sont triés à l'aide de Quicksort. Les tableaux d'objets sont également triés avec un Mergesort.

Ainsi Collections.sort semble utiliser le même algorithme de tri que Arrays.sort pour Objects.

Une autre question serait pourquoi un algorithme de tri différent est utilisé pour les tableaux primitifs que pour les tableaux d'objets?

Comme indiqué dans de nombreuses réponses.

Le tri rapide est utilisé par Arrays.sort pour trier les collections primitives car la stabilité n'est pas requise (vous ne saurez pas ou ne vous soucierez pas si deux entiers identiques ont été échangés dans le tri)

MergeSort ou plus spécifiquement Timsort est utilisé par Arrays.sort pour trier des collections d'objets. La stabilité est requise. Quicksort ne fournit pas de stabilité, Timsort le fait.

Collections.sort délègue à Arrays.sort, c'est pourquoi vous voyez le javadoc référençant le MergeSort.

Le tri rapide présente deux inconvénients majeurs en ce qui concerne le tri par fusion:

• Ce n'est pas stable alors qu'il s'agit de non primitif.
• Il ne garantit pas les performances n log n.

La stabilité n'est pas un problème pour les types primitifs, car il n'y a pas de notion d'identité distincte de l'égalité (de valeur).

La stabilité est un gros problème lors du tri d'objets arbitraires. C'est un avantage supplémentaire que Merge Sort garantit des performances n log n (temps) quelle que soit l'entrée. C'est pourquoi le tri par fusion est sélectionné pour fournir un tri stable (tri par fusion) pour trier les références d'objet.