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

Question

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

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

Answer 1

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

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

Answer 2

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

Answer 3

.NET использует QuickSort. Вы можете использовать Reflector для просмотра реализации в System.Collections.Generic.ArraySortHelper

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

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