¿Qué algoritmo de clasificación se utiliza en STL y .net búsqueda predeterminado biblioteca de la base?

Question

Ahora estoy trabajando en una versión imprived de fusión tipo. He implementado con C ++ y C #. A continuación, los comparó con el array.sort () algoritmo de ordenación y STL, respectivamente. En C ++ Tengo una (a veces mejor) resultado igual. Pero en C #, tuve que usar código no seguro para el uso de punteros. Aquí el performence no es muy comparable con orden predeterminado. Por lo tanto, quiero saber-
1. ¿Qué algoritmos se utilizan en STL y biblioteca de clases base de .NET? (Mejor con enlaces)
2. ¿códigos de protección causa performence problemas?
3. Cualquier suggessions para mí con respecto a la medición de la performence del nuevo algoritmo?

Answer 1

.NET utiliza una variación de Quicksort (mediana de 3 Quicksort de Sedgewick).

A menos que sea un experto en la clasificación, Me sorprendería si puede vencer a la clase a través de una amplia gama integrada de los datos (incluidos los conjuntos ordenados al azar, ya ordenadas y reverso). Recurrir a código no seguro es por lo general una mala idea ...

Answer 2

El STL especie puede depender de la aplicación, pero ( como dice la Wikipedia ) por lo general es introsort, una combinación de quicksort y heapsort. Debe tener una complejidad media de O (n log n) comparaciones.

Answer 3

.NET utiliza QuickSort. Puede usar Reflector para ver la implementación de System.Collections.Generic.ArraySortHelper

En la mayoría de los casos, QuickSort funcionará más rápido que mergesort, a pesar de que el tiempo de ejecución del peor caso es más largo. Ha habido algunas mejoras en QuickSort estándar, así que creo, pero no estoy seguro si se utiliza cualquiera de estos.

Me parece recordar STL utilizando QuickSort así, pero no estoy completamente seguro.