C# SortedDictionary Usage: Ordering and Performance

When you need a dictionary that keeps its keys in sorted order, SortedDictionary<TKey, TValue> is the standard .NET collection for that job. This article covers practical C# SortedDictionary usage: how to create and populate it, how ordering works, how to supply a custom comparer, and where its performance profile makes it a better choice than a plain Dictionary or a SortedList.

What SortedDictionary Provides

SortedDictionary<TKey, TValue> lives in the System.Collections.Generic namespace. It stores key-value pairs and maintains the keys in sorted order at all times. Every insertion, deletion, and lookup operates in O(log n) time because the underlying implementation is a balanced binary search tree (specifically, a red-black tree).

Unlike Dictionary<TKey, TValue>, which uses a hash table and has no defined iteration order, SortedDictionary guarantees that enumeration yields pairs in ascending key order. This makes it the natural choice when you need both fast key-based access and deterministic ordering without sorting manually after each change.

Basic Usage and Syntax

Creating a SortedDictionary is similar to creating a regular dictionary. The type parameters specify the key and value types.

using System.Collections.Generic;

var scores = new SortedDictionary<string, int>();
scores["Alice"] = 92;
scores["Bob"] = 85;
scores["Charlie"] = 88;

foreach (var pair in scores)
{
    Console.WriteLine($"{pair.Key}: {pair.Value}");
}

When you enumerate scores, the keys appear in alphabetical order: Alice, Bob, Charlie. Insertion order is irrelevant; the collection rebalances internally to keep the keys sorted.

Adding and removing items uses the same API as Dictionary. The indexer throws a KeyNotFoundException if you try to read a missing key, so use TryGetValue when the key might not exist.

if (scores.TryGetValue("David", out int davidScore))
{
    Console.WriteLine($"David scored {davidScore}");
}
else
{
    Console.WriteLine("David not found");
}

Ordering Behavior and Custom Comparers

By default, SortedDictionary uses the default comparer for the key type. For numeric types this means ascending numeric order; for strings it uses the current culture's string comparison rules. If you need a different ordering, you can pass an IComparer<TKey> implementation to the constructor.

For example, to sort keys in descending order, create a comparer that reverses the default comparison:

public class DescendingComparer<T> : IComparer<T> where T : IComparable<T>
{
    public int Compare(T x, T y) => y.CompareTo(x);
}

var descending = new SortedDictionary<string, int>(new DescendingComparer<string>());
descending["Alice"] = 92;
descending["Bob"] = 85;
descending["Charlie"] = 88;

foreach (var pair in descending)
{
    Console.WriteLine($"{pair.Key}: {pair.Value}");
}

This outputs Charlie, Bob, Alice. The comparer must be consistent with Equals for the key type: if Compare(x, y) == 0, then x.Equals(y) should return true and vice versa. Violating this rule causes keys that compare equal to be treated as duplicates, and the collection will reject or overwrite them unpredictably.

Custom comparers are also useful when you want case-insensitive string keys. Pass StringComparer.OrdinalIgnoreCase to the constructor:

var caseInsensitive = new SortedDictionary<string, int>(StringComparer.OrdinalIgnoreCase);
caseInsensitive["apple"] = 1;
caseInsensitive["Banana"] = 2;
caseInsensitive["CHERRY"] = 3;

foreach (var pair in caseInsensitive)
{
    Console.WriteLine($"{pair.Key}: {pair.Value}");
}

Here the keys are sorted using ordinal case-insensitive comparison, so the output is apple, Banana, CHERRY. Note that the original casing is preserved in the stored key, but lookup is case-insensitive.

Performance Characteristics and When to Use

SortedDictionary trades constant-time hash lookups for logarithmic-time operations. Insertion, deletion, and lookup are all O(log n). For small collections the difference is negligible, but as the number of elements grows, the logarithmic cost becomes more significant than the near-constant cost of a Dictionary.

Memory usage is also higher than a Dictionary because each node in the tree stores references to its children and the color flag used by the red-black tree algorithm. If you need to iterate in sorted order and the collection is large, SortedDictionary avoids the O(n log n) cost of sorting a Dictionary every time, but it pays a constant overhead per operation.

Use SortedDictionary when:

• You need to enumerate keys in sorted order frequently, and the collection changes between enumerations.
• You need to find the smallest or largest key quickly (via First() or Last() with LINQ, though this is O(log n) rather than O(1)).
• You are building a priority queue-like structure where keys represent priority and you need to repeatedly remove the lowest or highest key.

Avoid it when the ordering is only needed occasionally and the collection is large. In that case, a Dictionary plus a one-time sort of the keys is often faster and uses less memory.

SortedDictionary vs SortedList vs Dictionary

SortedList<TKey, TValue> also maintains sorted keys, but its internal implementation is a contiguous array of key-value pairs. This gives it different performance characteristics:

SortedList is more efficient when you build the collection once and then only read it, because insertion and deletion require shifting elements in the array. SortedDictionary is better when the collection changes frequently because tree rotations are localized and do not shift large blocks of memory.

In practice, if you need sorted enumeration and the collection size is under a few thousand elements, either works. For larger collections with frequent writes, SortedDictionary is usually the safer choice. If you do not need ordering at all, Dictionary is the simplest and fastest option.

Common Pitfalls and Edge Cases

One common mistake is assuming that SortedDictionary preserves insertion order. It does not. The order is always determined by the comparer, not by the sequence of Add calls. If you need both sorted order and insertion order, you must maintain a separate list or use a different data structure.

Another issue arises when the key type does not implement IComparable. The default comparer will throw an InvalidOperationException at runtime. You must provide a custom comparer for such types. For example, a custom class used as a key needs an explicit comparer:

public record Person(string Name, int Age);

public class PersonComparer : IComparer<Person>
{
    public int Compare(Person x, Person y) => x.Name.CompareTo(y.Name);
}

var people = new SortedDictionary<Person, string>(new PersonComparer());
people[new Person("Alice", 30)] = "Engineer";
people[new Person("Bob", 25)] = "Designer";

Without the comparer, this code fails because Person does not implement IComparable<Person>.

Also be aware that SortedDictionary uses the comparer to determine equality for keys. If two keys compare as equal, the second Add or indexer assignment overwrites the first. This is consistent with Dictionary behavior but can surprise developers who expect distinct objects with the same sort key to coexist.

Practical Example: Grouping by Sorted Keys

A common real-world use case is aggregating data by a sorted key. For instance, suppose you have a list of transactions and you want to group them by date, with dates in ascending order. SortedDictionary makes this straightforward:

var dailyTotals = new SortedDictionary<DateTime, decimal>();

foreach (var transaction in transactions)
{
    var date = transaction.Date.Date; // strip time
    if (dailyTotals.TryGetValue(date, out decimal total))
    {
        dailyTotals[date] = total + transaction.Amount;
    }
    else
    {
        dailyTotals[date] = transaction.Amount;
    }
}

foreach (var pair in dailyTotals)
{
    Console.WriteLine($"{pair.Key:yyyy-MM-dd}: {pair.Value:C}");
}

Because DateTime implements IComparable, the keys are automatically sorted from earliest to latest. The enumeration produces a chronological report without any additional sorting step.

If you later need to find the day with the highest total, you can iterate once and track the maximum. The sorted order does not directly help with that, but it ensures the output is readable and stable.

Handling Missing Keys Gracefully

When working with SortedDictionary, you will often need to handle missing keys. The indexer throws, but TryGetValue is the idiomatic way to check and retrieve in one step. You can also use ContainsKey if you only need to test existence, but that performs a separate lookup.

For scenarios where a default value is appropriate, you can use GetValueOrDefault with the CollectionsMarshal extension if you are on .NET 6 or later, but that works only with Dictionary, not SortedDictionary. For SortedDictionary, a simple pattern is:

if (!sortedDict.TryGetValue(key, out var value))
{
    value = defaultValue;
}

This avoids double lookups and keeps the code clear.

When Not to Use SortedDictionary

If your keys are already sorted in the order you need, or if you only need to sort once after a series of inserts, a List<KeyValuePair<TKey, TValue>> sorted with List.Sort can be more memory-efficient. Similarly, if you need to find a key by its position (e.g., the 10th smallest key), SortedList exposes direct index access, while SortedDictionary does not. SortedDictionary has no indexer for positional access; you must enumerate to reach a specific rank.

For concurrent access, neither SortedDictionary nor Dictionary is thread-safe for simultaneous writes. You must use a lock or a concurrent collection like ConcurrentDictionary, but ConcurrentDictionary does not maintain sorted order. If you need thread-safe sorted storage, you will need to combine a lock with SortedDictionary or use a custom structure.

Understanding these tradeoffs ensures you choose the right collection for your specific workload rather than defaulting to SortedDictionary just because it sounds more capable.