Qual algoritmo de classificação é usado em STL e pesquisa .net padrão biblioteca de base?

Question

Agora estou trabalhando em uma versão imprived de merge sort. I aplicaram com C ++ e C #. Em seguida, comparou-os com o tipo STL e algoritmo array.sort (), respectivamente. Em C ++ Eu tenho um resultado igual (às vezes melhor). Mas em C #, eu tive que usar o código inseguro para usar ponteiros. Aqui o performence não é muito comparável com a classificação padrão. Então, eu quero saber
1. Qual algoritmos são usados ??em STL e biblioteca de classes base do .NET? (Better com links)
2. códigos inseguros fazemos tem performence questões?
3. Qualquer suggessions para me sobre a medição da performence do novo algoritmo?

Answer 1

.NET usa uma variação do Quicksort (mediana de 3 Quicksort de Sedgewick).

A menos que você seja um especialista em classificação, eu ficaria surpreso se você pode bater o built-in Classificar em uma ampla gama de dados (incluindo conjuntos ordenados aleatoriamente, já encomendados e verso). Recorrer ao código inseguro é geralmente uma má idéia ...

Answer 2

O tipo STL pode depender da implementação, mas ( como wikipedia diz ) é geralmente introsort, uma combinação de quick e heapsort. Ele deve ter uma complexidade média de O (n log n) comparações.

Answer 3

.NET usa QuickSort. Você pode usar refletor para ver a implementação em System.Collections.Generic.ArraySortHelper

Na maioria dos casos, QuickSort irá correr mais rápido do que mergesort, mesmo que o tempo de execução do pior caso é mais longo. Houve algumas melhorias em QuickSort padrão, bem eu acho, mas eu não estou certo se algum destes são utilizados.

Eu pareço STL recordação usando QuickSort bem, mas eu não estou completamente certo.