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

Провел тест, оказались странные результаты

для SortedDictionary

Добавление закончено, за время 00:00:01.1544021 с.
Поиск закончен, за время 00:00:00.8580015 с.

для обычного Dictionary

Добавление закончено, за время 00:00:00.1404002 с.
Поиск закончен, за время 00:00:00.0624001 с.

Получается что обычный Dictionary раз в 10 быстрее как на добавление , так и на поиск по ключу. В чем преимущество SortedDictionary тогда ?

static void Main(string[] args)
{
var dict = new SortedDictionary<int,int>();

DateTime start = DateTime.Now;

for (int i = 1000000; i >=0; i--)
{
dict[i] = 0;
}

Console.WriteLine("Добавление закончено, за время {0} с.",
(DateTime.Now — start));


start = DateTime.Now;
for (int i = 0; i <= 1000000; i++)
{
if (dict.ContainsKey(i))
dict[i] = i;
}

Console.WriteLine("Поиск закончен, за время {0} с.",
(DateTime.Now — start));


Console.ReadKey();
}