C# Dictionary vs SortedDictionary: Which to Use?

When working with key-value pairs in C#, the choice between Dictionary and SortedDictionary often comes down to whether you need ordered iteration. Dictionary uses a hash table for average O(1) lookups, while SortedDictionary maintains keys in sorted order using a binary search tree, giving O(log n) operations. This article compares c# dictionary vs sorteddictionary to help you decide which fits your scenario.

What Dictionary Provides

Dictionary<TKey, TValue> is the go-to collection for fast key-based access. It stores entries in a hash table, so retrieval, insertion, and deletion are typically O(1) on average, assuming a good hash function. The tradeoff is that the iteration order is undefined. The runtime does not guarantee any particular sequence, and the order can change when the dictionary is resized or when items are removed and re-added.

var lookup = new Dictionary<string, int>();
lookup["banana"] = 2;
lookup["apple"] = 5;
lookup["cherry"] = 3;

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

The output may appear in insertion order in some runs, but that is coincidental and not part of the contract. If your code relies on a specific order, Dictionary is not safe.

What SortedDictionary Provides

SortedDictionary<TKey, TValue> keeps keys sorted at all times. It is implemented as a red-black tree, so every operation—lookup, insert, delete—runs in O(log n). The enumerator returns entries in ascending key order by default, using the default comparer for the key type unless you supply a custom one.

var sorted = new SortedDictionary<string, int>();
sorted["banana"] = 2;
sorted["apple"] = 5;
sorted["cherry"] = 3;

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

This reliably prints apple, banana, cherry. The ordering is guaranteed, which makes SortedDictionary suitable for scenarios like producing sorted reports or maintaining a leaderboard.

Key Differences at a Glance

The following table summarizes the most important distinctions:

Both collections require unique keys. Adding a duplicate key throws an ArgumentException. Neither collection is thread-safe for concurrent writes; you must synchronize access externally or use a concurrent collection.

Performance Considerations

The performance difference is not just about big-O notation. For small collections, the constant factors can dominate. A Dictionary with a few dozen entries will often outperform a SortedDictionary even when sorted order is needed, because the tree operations involve more pointer chasing and allocations. However, as the collection grows, the algorithmic difference becomes more significant.

If your workload is read-heavy and you rarely modify the collection after construction, you can build a Dictionary once and then sort the keys when you need ordered output. This gives you O(1) lookups during the hot path and only pays the sorting cost when required.

var dict = new Dictionary<string, int>();
// populate
var orderedKeys = dict.Keys.OrderBy(k => k, StringComparer.Ordinal).ToList();

This approach is often faster than using SortedDictionary if lookups vastly outnumber insertions and you only need sorted output occasionally.

Choosing Between Dictionary and SortedDictionary

Use Dictionary when:

• You need the fastest possible key lookup and don't care about iteration order.
• You are storing transient data that is accessed by key, such as a cache or a lookup table.
• The collection is large and the O(1) average access is critical.

Use SortedDictionary when:

• You need to enumerate entries in sorted order repeatedly.
• You frequently insert and delete items while always keeping the collection sorted.
• You want a guaranteed order without manually sorting after each mutation.

A common pattern is to use Dictionary for the primary data store and then create a sorted projection when needed. This works well when the sorted order is required only for a specific output, like a report or an API response.

Practical Example: Frequency Counter with Sorted Output

Suppose you are counting word frequencies in a document and want to display the results alphabetically. You can use a Dictionary to count and then sort, or use a SortedDictionary directly.

Using SortedDictionary:

var counts = new SortedDictionary<string, int>(StringComparer.OrdinalIgnoreCase);
foreach (var word in words)
{
    counts.TryGetValue(word, out int count);
    counts[word] = count + 1;
}

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

The comparer StringComparer.OrdinalIgnoreCase makes the keys case-insensitive and sorts them in ordinal order. If you used a Dictionary, you would need to call OrderBy on the keys before printing.

Custom Comparers and Ordering Semantics

SortedDictionary accepts an IComparer<TKey> in its constructor. This lets you control both the sort order and equality semantics. For example, you can sort strings by length instead of alphabetically:

var byLength = new SortedDictionary<string, int>(Comparer<string>.Create((a, b) => a.Length.CompareTo(b.Length)));

Be careful with comparers that are not consistent with equality. If the comparer returns 0 for two different keys, the dictionary will treat them as duplicates and throw when you try to add the second one. The default comparer for strings is case-sensitive and culture-aware, which may not be what you want for ordinal sorting. Use StringComparer.Ordinal or StringComparer.OrdinalIgnoreCase when you need deterministic, culture-independent ordering.

Memory and Allocation Behavior

SortedDictionary uses more memory per entry than Dictionary because each node in a red-black tree stores references to left and right children, the parent, and a color flag. Dictionary stores entries in a contiguous array with a hash bucket array. For large collections, the difference can be substantial. If memory is tight and you do not need ordering, Dictionary is the better choice.

Another subtle difference is that Dictionary rehashes and resizes its internal arrays as it grows, which can cause temporary memory spikes. SortedDictionary allocates nodes individually, so it grows more gradually but with more frequent small allocations. In high-throughput scenarios, this can affect garbage collection pressure.

If you need both fast lookups and sorted iteration, consider maintaining a Dictionary for lookups and a separate sorted structure (like a List that you sort on demand) when the data is relatively static. This hybrid approach avoids the per-operation cost of a tree while still giving you ordered output when needed.