Pourquoi Collections.trier utilisation Mergesort mais les Tableaux.le tri ne fonctionne pas?

Question

Je suis à l'aide du JDK-8 (x64). Pour Arrays.sort j'ai trouvé le suivant dans la documentation de Java:

L'algorithme de tri est un Double Pivot Quicksort par Vladimir Yaroslavskiy, Jon Bentley, et Joshua Bloch.`

Pour Collections.sort j'ai trouvé ceci:

Cette mise en œuvre est stable, l'adaptation, la itératif mergesort ... Cette mise en œuvre décharges de la liste dans un tableau, trie le tableau, et parcourt la liste réinitialisation de chaque élément à partir de la position correspondante dans le tableau.

Si Collections.sort utilise un tableau, pourquoi ne pas simplement appeler Arrays.sort ou utiliser à double pivot QuickSort? Pourquoi utiliser Mergesort?

Answer 1

L'API garantit un stable tri Quicksort n'offre pas. Cependant, lors du tri des valeurs primitives par leur ordre naturel, vous ne remarquerez pas la différence des valeurs primitives n'ont aucune identité. Par conséquent, le tri rapide est utilisé pour des primitifs tableaux comme il est légèrement plus efficace.

Pour les objets, vous remarquerez peut-être, lorsque les objets qui sont considérés comme égaux selon leur equals de la mise en œuvre ou l'fournis Comparator changer leur ordre. Par conséquent, Quicksort est pas une option. Ainsi, une variante de MergeSort est utilisé, le courant versions de Java utiliser TimSort. Cela s'applique à tous les deux, Arrays.sort et Collections.sort, mais avec Java 8, List lui-même peut remplacer les algorithmes de tri.

Answer 2

Je ne sais pas à propos de la documentation, mais la mise en œuvre de l' java.util.Collections#sort dans Java 8 (HotSpot) qui va comme ceci:

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

Et List#sort a cette mise en œuvre:

@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#sort utilise Arrays#sort (des éléments d'objet) en coulisses. Cette implémentation utilise la fusion de tri ou tim tri.

Answer 3

Selon la Javadoc, seule primitive tableaux sont triés à l'aide de Quicksort. Tableaux d'objets, sont triés avec un Mergesort.

Afin De Collections.trier semble utiliser le même algorithme de tri sous la forme de Tableaux.trier les Objets.

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