Quale algoritmo di ordinamento viene utilizzato in STL e .NET libreria di base di ricerca predefinito?

Question

Ora sto lavorando su una versione imprived di merge sort. Ho implementato con C ++ e C #. Poi confrontato con l'algoritmo Array.sort () rispettivamente stl ordinamento e. In C ++ ho ottenuto un (a volte meglio) risultato uguale. Ma in C #, ho dovuto usare il codice non sicuro per l'utilizzo di puntatori. Qui il performence non è molto paragonabile con ordinamento predefinito. Quindi, voglio sapere-
1. Quali algoritmi sono utilizzati in STL e libreria di classi di base .NET? (Meglio con collegamenti)
2. fare i codici non sicuri ha performence problemi?
3. Eventuali suggessions per me per quanto riguarda la misurazione della performence del nuovo algoritmo?

Answer 1

.NET utilizza una variante del Quicksort (mediana di Sedgewick di 3 Quicksort).

A meno che non sei un esperto in ordinamento, sarei sorpreso se si può battere la Sort in un'ampia gamma built-in dei dati (inclusi insiemi ordinati a caso, già ordinati e retromarcia). Il ricorso al codice non sicuro è di solito una cattiva idea ...

Answer 2

Lo STL tipo può dipendere l'attuazione, ma ( come dice wikipedia ) di solito è introsort, una combinazione di quicksort e heapsort. Deve avere una complessità media di O (n log n) confronti.

Answer 3

.NET utilizza QuickSort. È possibile utilizzare Reflector per visualizzare l'implementazione in System.Collections.Generic.ArraySortHelper

Nella maggior parte dei casi, QuickSort sarà correre più veloce di MergeSort, anche se il tempo di esecuzione nel caso peggiore è più lungo. Ci sono stati alcuni miglioramenti sul QuickSort standard così credo, ma non sono certo se vengono utilizzati uno di questi.

Mi sembra di ricordare STL usando QuickSort pure, ma io non sono del tutto certo.