Pourquoi Collections.sort utilise le tri par fusion au lieu du tri rapide?

Nous savons que le tri rapide est l'algorithme de tri le plus rapide.

Le JDK6 collections.sortutilise l'algorithme de tri par fusion au lieu du tri rapide. Mais Arrays.sort utilise un algorithme de tri rapide.

Quelle est la raison pour laquelle Collections.sort utilise le tri par fusion au lieu du tri rapide?

Très probablement de Josh Bloch § :

J'ai écrit ces méthodes, donc je suppose que je suis qualifié pour répondre. Il est vrai qu'il n'existe pas de meilleur algorithme de tri. QuickSort présente deux lacunes majeures par rapport au tri par fusion:

1. Ce n'est pas stable (comme l'a noté parsifal).

2. Il ne garantit pas les performances n log n; il peut se dégrader en performances quadratiques sur les entrées pathologiques.

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). Et la possibilité d'un comportement quadratique n'a pas été considérée comme un problème en pratique pour l'implémentation de Bentely et McIlroy (ou ultérieurement pour Dual Pivot Quicksort ), c'est pourquoi ces variantes QuickSort ont été utilisées pour les sortes primitives.

La stabilité est un gros problème lors du tri d'objets arbitraires. Par exemple, supposons que vous ayez des objets représentant des e-mails et que vous les triiez d'abord par date, puis par expéditeur. Vous vous attendez à ce qu'ils soient triés par date dans chaque expéditeur, mais cela ne sera vrai que si le tri est stable. C'est pourquoi nous avons choisi de fournir un tri stable (Merge Sort) pour trier les références d'objets. (D'un point de vue technique, plusieurs tris séquentiels stables entraînent un ordre lexicographique des clés dans l'ordre inverse des tris: le tri final détermine la sous-clé la plus significative.)

C'est un avantage supplémentaire que Merge Sort garantit des performances n log n (temps) quelle que soit l'entrée. Bien sûr, il y a un inconvénient: le tri rapide est un tri "en place": il ne nécessite que log n espace externe (pour maintenir la pile d'appels). Fusionner, trier, par contre, nécessite un espace externe O (n). La variante TimSort (introduite dans Java SE 6) nécessite beaucoup moins d'espace (O (k)) si le tableau d'entrée est presque trié.

En outre, ce qui suit est pertinent:

L'algorithme utilisé par java.util.Arrays.sort et (indirectement) par java.util.Collections.sort pour trier les références d'objet est un "mergesort modifié (dans lequel la fusion est omise si l'élément le plus élevé de la sous-liste inférieure est inférieur à l'élément le plus bas de la sous-liste haute). " Il s'agit d'un tri stable raisonnablement rapide qui garantit les performances O (n log n) et nécessite un espace supplémentaire O (n). En son temps (il a été écrit en 1997 par Joshua Bloch), c'était un bon choix, mais aujourd'hui, on peut faire beaucoup mieux.

Depuis 2003, le tri par liste de Python utilise un algorithme appelé timsort (d'après Tim Peters, qui l'a écrit). Il s'agit d'un tri de fusion itératif, adaptatif et stable qui nécessite beaucoup moins de n comparaisons log (n) lorsqu'il est exécuté sur des tableaux partiellement triés, tout en offrant des performances comparables à un tri de fusion traditionnel lorsqu'il est exécuté sur des tableaux aléatoires. Comme toutes les fusions appropriées, timsort est stable et s'exécute en temps O (n log n) (pire des cas). Dans le pire des cas, timsort nécessite un espace de stockage temporaire pour n / 2 références d'objet; dans le meilleur des cas, il ne nécessite qu'une petite quantité d'espace constante. Comparez cela avec l'implémentation actuelle, qui nécessite toujours un espace supplémentaire pour n références d'objet, et bat n log n uniquement sur des listes presque triées.

Timsort est décrit en détail ici: http://svn.python.org/projects/python/trunk/Objects/listsort.txt .

L'implémentation originale de Tim Peters est écrite en C. Joshua Bloch l'a portée de C à Java et a finalement testé, comparé et optimisé le code résultant en profondeur. Le code résultant est un remplacement instantané de java.util.Arrays.sort. Sur des données hautement ordonnées, ce code peut s'exécuter jusqu'à 25 fois plus vite que l'implémentation actuelle (sur la VM du serveur HotSpot). Sur des données aléatoires, les vitesses des anciennes et nouvelles implémentations sont comparables. Pour les listes très courtes, la nouvelle implémentation est nettement plus rapide que l'ancienne même sur des données aléatoires (car elle évite la copie inutile de données).

Voir également Java 7 utilise-t-il Tim Sort pour les tableaux de méthodes. .

Il n'y a pas un seul «meilleur» choix. Comme pour beaucoup d'autres choses, il s'agit de compromis.