C# Dictionary vs SortedDictionary: Which to Use?
Compare C# Dictionary and SortedDictionary: ordering guarantees, lookup performance, memory behavior, and practical guidance for choosing between them.

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 red-black tree, giving O(log n) operations. This article compares the two collections 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 simple cases, 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:
| Aspect | Dictionary | SortedDictionary |
|---|---|---|
| Underlying structure | Hash table | Red-black tree |
| Lookup complexity | O(1) average | O(log n) |
| Insert/delete complexity | O(1) average | O(log n) |
| Iteration order | Undefined | Sorted by key |
| Memory overhead | Typically lower per entry | Higher per node (tree pointers) |
| Custom comparer | IEqualityComparer<TKey> via constructor | IComparer<TKey> via constructor |
Both collections require unique keys. Adding a duplicate key with the Add method throws an ArgumentException; using the indexer with an existing key updates the value instead. 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 can be 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
Dictionary accepts an IEqualityComparer<TKey> in its constructor, while SortedDictionary accepts an IComparer<TKey>. For SortedDictionary, the comparer controls both 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, SortedDictionary will treat them as duplicates, so Add will throw when you try to add the second one. For SortedDictionary, string ordering uses a case-sensitive, culture-aware comparison (Comparer<string>.Default), 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.
Try matching browser tools
All toolsSmall utilities that fit C# work — they run entirely in this browser tab, so nothing you paste leaves your device.
Related C# guides
All C# guidesC# Dispose vs Destructor: Key Differences Explained
c# dispose vs destructor: Understand the difference between Dispose and destructors in C#, when each runs, and how to manage unmanaged resources correctly.
C# Variable Declaration: Syntax and Practical Usage
Learn how to declare variables in C# with explicit types, var, and nullable annotations, and understand how defaults, scope, and readability affect your choices.
C# Primary Constructors for Classes: Syntax and Usage
Learn how to use C# primary constructors for classes: syntax, initialization, dependency injection, and limitations with practical examples.
C# IComparer: Custom Sorting with IComparer<T>
Learn how to implement IComparer<T> in C# to define custom sort order for arrays and lists, handle nulls, and avoid common performance pitfalls.
More in C#
All C# guidesThe guides filed next to this one in C#, in library order.