Java et .NET: Pourquoi différents algorithmes de tri sont-ils utilisés par défaut?

Je me demande simplement pourquoi Javaet .NET Frameworkutilise différents algorithmes de tri par défaut.

En Java, il Array.Sort() utilise l' algorithme de tri par fusion et comme le dit Wikipedia.com :

En Java, les méthodes Arrays.sort () utilisent le tri par fusion ou un tri rapide en fonction des types de données et pour l'efficacité de l'implémentation, passez au tri par insertion lorsque moins de sept éléments de tableau sont triés

Dans .NET Framework Array.Sort/List.Sort() utilise le tri rapide comme algorithme de tri par défaut ( MSDN ):

List.Sort () utilise Array.Sort, qui utilise l'algorithme QuickSort. Cette implémentation effectue un tri instable; c'est-à-dire que si deux éléments sont égaux, leur ordre risque de ne pas être conservé. En revanche, un tri stable préserve l'ordre des éléments égaux.

En regardant le grand tableau "Comparaison des algorithmes" , nous pouvons voir que les deux algorithmes ont un comportement assez différent du point de vue du pire cas et de l'utilisation de la mémoire:

Les deux Javaet .NETsont d'excellents cadres pour le développement de solutions d'entreprise, les deux ont des plates-formes de développement intégré. Alors pourquoi utilisent-ils différents algorithmes de tri par défaut, des réflexions?

Aussi déterministe que soient les ordinateurs eux-mêmes, l'ingénierie informatique n'est pas une science exacte. Deux personnes, ayant le même domaine de problème, effectueront une analyse et développeront deux solutions différentes qui satisfont toutes les contraintes du problème. Il peut être difficile, voire impossible, de déterminer empiriquement lequel d'entre eux est "meilleur" dans le cas général.

Je suppose que le .NET QuickSort est superposé à quelque chose dans les MFC ou l'API Windows, et est probablement hérité de versions beaucoup plus anciennes de Windows où l'avantage multi-threadable de MergeSort n'aurait même pas été pris en compte pour les ordinateurs de le jour. ( EDIT: ce n'est pas le cas, bien que les développeurs Microsoft soient des fans de QuickSort depuis longtemps, comme en témoigne ce choix d'implémentation du tri depuis MS-DOS).

Java, qui ne peut utiliser aucune implémentation spécifique à la plate-forme, car Java a été conçu à partir de zéro pour être complètement indépendant de la plate-forme, est allé d'une manière différente. Qui sait pourquoi MergeSort est arrivé en tête; ma conjecture est que l'implémentation a remporté une sorte de compétition de performance par rapport à d'autres sortes que les développeurs ont imaginées, ou bien qu'un MergeSort O (n) -espace avait l'air mieux sur le papier en termes de performances dans le meilleur et le pire des cas (MergeSort n'a pas de talon d'Achille concernant la sélection d'éléments comme QuickSort, et son meilleur cas est une liste triée alors que c'est souvent le pire de QuickSort). Je doute que les avantages du multithreading aient été initialement envisagés, mais la mise en œuvre actuelle pourrait bien être multithread.

Différentes équipes de développement dans deux sociétés différentes sont parvenues à des conclusions différentes concernant le cas d'utilisation habituel de leurs frameworks et composants et ont décidé de les mettre en œuvre en conséquence.

Essentiellement, chaque entreprise a fait son analyse, examiné sa clientèle et pris des décisions différentes en conséquence.

Vous ne pouvez pas vous attendre à une analyse par différentes entreprises et équipes, en utilisant différentes hypothèses et données brutes pour arriver à la même conclusion.

Cette question est un peu dépassée, car Java utilise désormais Timsort (à partir de Java 7)

Parmi les algorithmes spécifiques mentionnés:

• Quicksort a des performances défavorables dans le pire des cas à O (n ^ 2), mais est un peu plus léger / moins consommateur de mémoire et offre donc de meilleures performances dans un cas typique.

• Mergesort a garanti les performances les plus défavorables à O (n log n), mais comporte un peu plus de surcharge et de mémoire. Il est également automatiquement stable (c'est-à-dire qu'il maintient des éléments égaux dans le même ordre).

Les concepteurs Java semblent en général être un peu plus conservateurs / concentrés sur la «bonne chose», il n'est donc pas surprenant qu'ils aient choisi Mergesort parmi les deux car il offre de meilleures garanties.

Vous ne savez pas pourquoi Microsoft a choisi Quicksort, peut-être pensaient-ils que cela les rendrait mieux dans certains micro-benchmarks?