День сто сорок шестой. #ЗаметкиНаПолях
Коллекции в C#
6. Сортировка коллекций
В .Net реализованы следующие основные типы отсортированных коллекций:
1. SortedSet<T>
Поддерживает отсортированный порядок, не влияя на производительность вставки и удаления. Повторяющиеся элементы не допускаются. Изменение отсортированных значений существующих элементов не поддерживается и может привести к неожиданному поведению. Потокобезопасная версия - ImmutableSortedSet<T>.

2. SortedList<TKey,TValue> и SortedDictionary<TKey,TValue>
SortedList<TKey, TValue> - это массив пар ключ/значение с поиском за время O(log n). В этом он похож на SortedDictionary<TKey, TValue>. Два класса имеют похожие объектные модели, и оба имеют время извлечения O(log n). Различаются они в использовании памяти и скорости вставки и удаления:
- SortedList использует меньше памяти.
- SortedDictionary быстрее вставляет и удаляет несортированные данные (O(log n) против O(n) для SortedList).
- Если список заполняется сразу из отсортированных данных, SortedList работает быстрее.
SortedList поддерживает эффективный индексированный поиск ключей и значений через коллекции, возвращаемые свойствами Keys и Values. Нет необходимости повторно создавать списки при обращении к свойствам, поскольку они являются просто оболочками для внутренних массивов ключей и значений. В следующем коде показано использование индексатора свойства Values для извлечения значения из отсортированного списка строк:

string v = mySortedList.Values[3];

Элементы SortedList могут быть извлечены как объекты KeyValuePair<TKey, TValue>, для SortedDictionary – как KeyValuePair<TKey, TValue> или как необобщённые объекты DictionaryEntry.
Объекты ключей должны быть неизменяемыми, если они используются в качестве ключей в SortedList или SortedDictionary. Каждый ключ в должен быть уникальным, не нулевым. Значение может быть нулевым, если TValue - ссылочный тип.
SortedList и SortedDictionary требуют реализации компаратора для сортировки и выполнения сравнений. Компаратор по умолчанию Comparer<T>.Default проверяет, реализует ли тип ключа IComparable<T>, и использует эту реализацию, если она доступна. Если нет, он проверяет, реализует ли тип ключа IComparable. Если тип ключа не реализует ни один из этих интерфейсов, вы можете указать параметр-компаратор, реализующий IComparer<T>, в перегруженной версии конструктора.
Когда элементы добавляются в SortedList, емкость автоматически увеличивается по мере необходимости путем перераспределения внутреннего массива. Емкость можно уменьшить, вызвав TrimExcess или явно указав свойство Capacity. Уменьшение емкости перераспределяет память и копирует все элементы в SortedList.
Оператор foreach перебирает объекты типа элементов в коллекции. Поскольку элементы SortedList и SortedDictionary являются парами ключ/значение, foreach перебирает элементы KeyValuePair<TKey, TValue>:

foreach (KeyValuePair<int, string> kvp в sortedList)
{
  Console.WriteLine("{0} = {1}", kvp.Key, kvp.Value);
}

Кроме того, можно использовать метод Sort для несортированных списков:
- Sort(IComparer<T> comparer)
Cортирует все элементы, используя указанный компаратор.
- Sort(int index, int count, IComparer<T> comparer)
Cортирует элементы в диапазоне (count элементов, начиная с index), используя указанный компаратор.
- Sort()
Сортирует все элементы, используя компаратор по умолчанию.
- Sort(Comparison<T> cmp)
Сортирует все элементы списка, используя делегат сравнения. Делегат сравнения вида int Comparison<in T>(T x, T y) должен возвращать значение меньше 0, если x<y, больше 0, если x>y и 0, если x=y.
Например:

var list = new List<int>{2,4,3,1};
// сортировка по возрастанию (по умолчанию)
list.Sort(); // 1,2,3,4
// используем лямбда-выражение для сортировки по убыванию
list.Sort((x,y) => y-x); // 4,3,2,1

Источник: https://docs.microsoft.com/ru-ru/dotnet/api/system.collections.generic