Самая быстрая сортировка динамической структуры данных

[Mixim]

Добрый день\вечер\ночь. Стоит задача: "имеется динамическая структура данных. Реализовать для неё наиболее оптимальный метод сортировки". Понятно, что в C# у стандартного класса List есть метод Sort(), но данная динамическая структура никак не привязывается к этому классу, поэтому нужно все делать "своими ручками". Знаю некоторые элементарные сортировки, которые можно применить в том числе и к динамическим структурам: "пузырьковая"(одна из наиболее медленных сортировок даже для массивов), "метод вставок" и ещё несколько штук. Подскажите, какой метод лучше использовать для сортировки, может за последние годы были разработаны более рациональные методы, чем "пузырьковая" сортировка и сортировка "методом вставок"?

[Руслантус]

http://algolist.manual.ru/sort/faq/q12.php


В общем случае:
Малые массивы/списки - менее 20 элементов => InsertSort
Большие массивы => QuickSort
Длинные списки/файлы => MergeSort

Для сортировок сравнениями давно доказана теорема о максимальном быстродействии: Omega(nlogn) операций.

Если количество возможных различных ключей ненамного больше их общего
числа - то наибыстрейшей будет распределяющая сортировка и ее вариации:

Radix sort - 'радиксная', или 'распределяющая' сортировка.
Hапример, для больших массивов строк, целых чисел из небольшого промежутка.
Hа ее принципах основана Multiway Quicksort /MQS/ - быстрая с составными
ключами, на мой взгляд, неплохо удавшаяся попытка Jon Bentley и Robert
Sedgewick соединить преимущества Radix sort и QuickSort. Есть и другие шаги
в этом направлении..

Существует еще очень много различных сортировок, которые выходят за рамки
FAQ'а.
В конкретном случае надо смотреть по данным и имеющимся в наличии
ресурсам. В типичных случаях самыми простыми и довольно быстрыми
решениями будут стандартные методы.