Which sorting algorithm is used in stl and .net ba

问题:

I am now working on an imprived version of merge sort. I implemented it with C++ and C#. Then compared them with the stl sort and array.sort() algorithm respectively. In C++ I have got an equal (sometimes better) result. But in C#, I had to use unsafe code for using pointers. Here the performence is not that much comparable with default sort. So, I want to know-

1. Which algorithms are used in stl and .net base class library?(Better with links)
2. Do unsafe codes has performence issues?
3. Any suggessions for me regarding measuring the performence of the new algorithm?

回答1:

.NET uses a variation of Quicksort (Sedgewick's median of 3 Quicksort).

Unless you are an expert in sorting, I would be surprised if you can beat the built-in Sort over a wide range of data (including random, already ordered and reverse ordered sets). Resorting to unsafe code is usually a bad idea...

回答2:

The STL sort may depend on the implementation, but (as wikipedia says) it is usually introsort, a combination of quicksort and heapsort. It must have an average complexity of O(n log n) comparisons.

回答3:

.NET uses QuickSort. You can use Reflector to view the implementation in System.Collections.Generic.ArraySortHelper

In most cases, QuickSort will run faster than MergeSort, even though the worst-case execution time is longer. There have been some improvements on standard QuickSort as well I think, but I'm not certain if any of these are used.

I seem to recall STL using QuickSort as well, but I'm not completely certain.