Quel algorithme de tri est utilisé dans stl et bibliothèque de base .net recherche par défaut?

Question

Je travaille maintenant sur une version imprived de tri fusion. Je mis en œuvre avec C ++ et C #. Ensuite, par rapport à leur genre stl et algorithme array.sort () respectivement. En C ++ j'ai un résultat égal (parfois plus). Mais en C #, je devais utiliser le code dangereux pour l'utilisation de pointeurs. Ici, le performence est pas beaucoup comparable à tri par défaut. Je veux donc savoir-
1. Quels algorithmes sont utilisés dans stl et bibliothèque de classes de base .net? (Mieux avec des liens)
2. Ne codes dangereux a performence questions?
3. Toute suggessions pour moi en ce qui concerne la mesure de la performence du nouvel algorithme?

Answer 1

.NET utilise une variation de Quicksort (la médiane de Sedgewick 3 Quicksort).

Sauf si vous êtes un expert en matière de tri, je serais surpris si vous pouvez battre le haut-Trier sur une large gamme de données (y compris au hasard, déjà commandés et inverse ensembles ordonnés). Le recours à un code dangereux est généralement une mauvaise idée ...

Answer 2

Le tri STL peut dépendre de la mise en œuvre, mais (comme wikipedia dit ), il est généralement introsort, une combinaison de tri rapide et heapsort. Il doit avoir une complexité moyenne des comparaisons O (n log n).

Answer 3

.NET utilise QuickSort. Vous pouvez utiliser réflecteur pour voir la mise en œuvre System.Collections.Generic.ArraySortHelper

Dans la plupart des cas, QuickSort va courir plus vite que mergesort, même si le pire des cas, le temps d'exécution est plus longue. Il y a eu quelques améliorations QuickSort standard et je pense, mais je ne suis pas certain si l'un de ceux-ci sont utilisés.

Je me souviens STL en utilisant QuickSort aussi bien, mais je ne suis pas tout à fait certain.