.NET Framework 4.5
Sorted Collection Types

The System.CollectionsSortedList class, the System.Collections.GenericSortedListTKey, TValue generic class, and the System.Collections.GenericSortedDictionaryTKey, TValue generic class are similar to the Hashtable class and the DictionaryTKey, TValue generic class in that they implement the IDictionary interface, but they maintain their elements in sort order by key, and they do not have the O(1) insertion and retrieval characteristic of hash tables. The three classes have several features in common:

The following table lists some of the differences between the two sorted list classes and the SortedDictionaryTKey, TValue class.

SortedList nongeneric class and SortedListTKey, TValue generic class

SortedDictionaryTKey, TValue generic class

The properties that return keys and values are indexed, allowing efficient indexed retrieval.

No indexed retrieval.

Retrieval is O(log n).

Retrieval is O(log n).

Insertion and removal are generally O(n); however, insertion is O(1) for data that are already in sort order, so that each element is added to the end of the list. (This assumes that a resize is not required.)

Insertion and removal are O(log n).

Uses less memory than a SortedDictionaryTKey, TValue.

Uses more memory than the SortedList nongeneric class and the SortedListTKey, TValue generic class.

For sorted lists or dictionaries that must be accessible concurrently from multiple threads, you can add sorting logic to a class that derives from ConcurrentDictionaryTKey, TValue.


For values that contain their own keys (for example, employee records that contain an employee ID number), you can create a keyed collection that has some characteristics of a list and some characteristics of a dictionary by deriving from the KeyedCollectionTKey, TItem generic class.

Starting with the .NET Framework 4, the SortedSetT class provides a self-balancing tree that maintains data in sorted order after insertions, deletions, and searches. This class and the  HashSetT class implement the ISetT interface.