Какой алгоритм сортировки используется в поиске по умолчанию в stl и .net base library?

Question

Сейчас я работаю над усовершенствованной версией сортировки слиянием.Я реализовал это с помощью C ++ и C #.Затем сравнил их с алгоритмом stl sort и array.sort() соответственно.В C ++ я получил равный (иногда лучший) результат.Но в C # мне пришлось использовать небезопасный код для использования указателей.Здесь производительность не настолько сопоставима с сортировкой по умолчанию.Итак, я хочу знать-

1.Какие алгоритмы используются в stl и библиотеке базовых классов .net?(Лучше со ссылками)
2.Есть ли у небезопасных кодов проблемы с производительностью?
3.Есть какие-нибудь предложения для меня относительно измерения производительности нового алгоритма?

Answer 1

.NET использует разновидность быстрой сортировки (медиана по Седжвику составляет 3 быстрой сортировки).

Если вы не являетесь экспертом в сортировке, я был бы удивлен, если бы вы смогли превзойти встроенную сортировку по широкому диапазону данных (включая случайные, уже упорядоченные и наоборот упорядоченные наборы).Прибегать к небезопасному коду обычно плохая идея...

Answer 2

Сортировка STL может зависеть от реализации, но (как говорится в Википедии) обычно это самосортировка, комбинация быстрой сортировки и сортировки кучно.Он должен иметь среднюю сложность O (n log n) сравнений.

Answer 3

.NET использует быструю сортировку.Вы можете использовать Отражатель чтобы просмотреть реализацию в системе.Коллекции.Универсальный.ArraySortHelper

В большинстве случаев быстрая сортировка будет выполняться быстрее, чем сортировка слиянием, даже несмотря на то, что в наихудшем случае время выполнения больше.Я думаю, что также были некоторые улучшения в стандартной быстрой сортировке, но я не уверен, используется ли что-либо из этого.

Кажется, я припоминаю, что STL также использует быструю сортировку, но я не совсем уверен.