Dictionary<TKey, TValue> is fast, but it has no notion of order. The moment you iterate it, you get keys in whatever sequence the hash table happens to bucket them, which is effectively random for the reader. SortedDictionary<TKey, TValue> and SortedList<TKey, TValue> fix that. Both store key/value pairs in ascending key order so iteration is predictable and range queries are possible. They reach the same outcome through two very different internal designs, which is why both exist instead of just one.

Both types live in System.Collections.Generic and both implement IDictionary<TKey, TValue>. From the outside they look almost identical: you call Add, you index by key, you check ContainsKey, you iterate and get sorted pairs. Swap one for the other in working code and most of it keeps compiling.

The difference is the data structure underneath.

SortedDictionary<TKey, TValue> uses a self-balancing binary search tree (a red-black tree in the current .NET implementation). Every key/value pair is a tree node with two child pointers and some bookkeeping bits. Lookups, inserts, and removals all walk from the root down to a leaf, which costs O(log n) comparisons.

SortedList<TKey, TValue> uses two parallel arrays: one for keys (kept sorted) and one for values (kept in matching positions). Lookups use binary search on the keys array, which is also O(log n). Inserts and removals, though, have to shift the trailing elements of both arrays to keep them packed and sorted, which costs O(n) in the worst case.

That single design difference cascades into every other property: memory per entry, cache friendliness, enumeration speed, growth behavior, and the kinds of workloads each is good at. The rest of this lesson walks through both, side by side, with the same E-Commerce examples so the trade-offs stay concrete.

The diagram shows the choice. You start with "I want a map sorted by key." From there, frequent mutation pushes you toward SortedDictionary, and a mostly-read pattern with smaller data pushes you toward SortedList. The rest of the lesson fills in why.

Both types have the same constructor shapes: empty, with an initial capacity (for SortedList only), with an existing dictionary to copy, and with a custom comparer for the key type. The simplest form takes no arguments.

The output is alphabetical by key (APPLE, BREAD, COFFEE, MILK), not insertion order. That's the whole point. The dictionary kept the entries in the order defined by string's default comparer, which for ASCII letters is alphabetical.

SortedList looks identical at the call site:

Same code, same output. If a reader sees only the foreach they can't tell which one was used. That symmetry is intentional: the API is part of the IDictionary<TKey, TValue> contract, and both classes implement it the same way for the operations they have in common.

What's not visible here is the cost of each Add. In SortedDictionary, each insert walks down the tree (O(log n)) and may trigger rotations to keep the tree balanced. In SortedList, each insert does a binary search to find the right position (O(log n)) and then shifts every element after that position one slot to the right in both the keys array and the values array (O(n)). Adding 1,000 random keys to a SortedList does roughly 500,000 element shifts. Adding the same keys to a SortedDictionary does roughly 10,000 comparisons and zero shifts.

Add throws ArgumentException if the key already exists. To overwrite or insert, use the indexer instead:

The indexer is "insert or replace": if the key is present it replaces, if not it inserts. Reading an indexer for a missing key throws KeyNotFoundException, the same way Dictionary does. The behavior is identical between SortedDictionary and SortedList, so the indexer is the right tool when you don't know whether a key is already there.

SortedDictionary stores its entries in a red-black tree, which is a binary search tree with extra coloring rules that keep the tree's height within 2 log(n + 1). The exact rules of red-black trees are not the point of this lesson. What matters is the shape and the cost profile that shape gives you.

The diagram shows a five-entry SortedDictionary after the keys APPLE, BREAD, COFFEE, MILK, SUGAR have been inserted. Every node holds one key/value pair. The left subtree of any node holds keys that compare less than the node's key; the right subtree holds keys that compare greater. To find MILK, the lookup compares against COFFEE (greater, go right), then against MILK (match, done). Two comparisons, one for each level of depth.

For 1,000 entries the tree is roughly 10 levels deep, so a lookup is at most about 10 comparisons. For 1,000,000 entries it's about 20. That's what "O(log n) with a small constant" actually feels like in practice.

Inserts work the same way: walk down to where the key would belong, hang a new node off the appropriate leaf, then rebalance if the local structure has become too lopsided. Rebalancing is a small constant number of pointer rotations per insert, amortized to O(1) on average per operation. Removals are similar: find the node, splice it out, rebalance if needed.

Two things follow from this design. First, the per-entry memory cost is high: each node holds a key, a value, two child pointers, a parent pointer, and a color bit. On a 64-bit runtime that's roughly 40 bytes of overhead per entry on top of the key and value themselves. For a million int-to-int entries you're paying around 50 megabytes of overhead. Second, enumeration is slower than for an array-backed structure, because each step has to walk to the next in-order node by following pointers, which is not as cache-friendly as a sequential array scan.

The growth behavior is also nice and predictable. There's no "resize" event the way there is for hash tables or arrays. Each Add allocates one node and links it in. Memory usage grows linearly with the number of entries, with no large reallocation pauses.

DateOnly has a sensible default comparer (chronological order), so the dictionary iterates orders from earliest to latest without any extra work from the caller. The tree structure handles the ordering internally. Inserts can come in any sequence, and the tree rebalances to keep lookups logarithmic.

SortedList looks deceptively similar from the outside but is built from two arrays: a TKey[] for keys (always kept sorted) and a TValue[] for values (matched position by position with the keys array).

The diagram shows the same five entries from earlier, but stored as two arrays. To find MILK, the lookup does a binary search on the keys array: compare index 2 (COFFEE), go right; compare index 3 (MILK), match; return values[3] = 3.49. That's O(log n) comparisons, same as the tree, but the comparisons are happening on a contiguous array, which is friendlier to the CPU's cache than chasing pointers between heap nodes.

Inserts and removals are where the story changes. To insert CHEESE (which sorts between BREAD and COFFEE), the runtime has to:

That shift is the O(n) part. For a list of 1,000 entries with an insert near the front, you move roughly 1,000 elements. For 1,000,000 entries, you move roughly 1,000,000. Random-position inserts into a large SortedList are the slow path.

The flip side is that storage is cheap. The arrays themselves are contiguous, so there's no per-node overhead like the tree pointers and color bit. For a million int-to-int entries, the storage is roughly two 4-million-byte arrays plus a small header. Enumeration is also fast because the keys and values are laid out sequentially in memory, which the CPU loves.

This is a textbook good fit for SortedList. The data is small (50 states max), it's loaded once at startup, and most operations are reads or iteration. Inserts are rare. Memory is minimal. The collection-initializer syntax (with { key, value }) works for any IDictionary<TKey, TValue>, so the two types accept it identically.

The SortedList.Capacity property exposes this and is read-write. Setting Capacity to a smaller value trims unused slots, which is useful if you built the list up and then need to hold it for a long time.

Setting Capacity = list.Count is the trim operation, though .NET's optimizer will refuse the assignment if it would shrink below Count. Use this when you have a long-lived list that started large and ended small. SortedDictionary has no equivalent because it doesn't pre-allocate, it grows one node at a time.

Because both implement IDictionary<TKey, TValue>, the day-to-day API is identical for the operations that matter most.

Every line here works identically against SortedList<string, int>. The signatures, return types, and exception behavior are part of the shared interface. The performance differs (Remove is O(log n) on the dictionary and O(n) on the list because of the shift after removal), but the code reads the same.

TryGetValue is the safest read pattern because it does the lookup once and signals miss versus hit through a bool return. Reading the indexer for a missing key throws KeyNotFoundException, which is fine when a missing key is a programming error but wrong when "key might not exist" is a normal case. Use the indexer when you know the key is there, use TryGetValue when you don't.

Count returns the number of entries. It's O(1) for both types (each tracks its own count internally). Clear() removes every entry, also identical in both.

Clear doesn't shrink the underlying arrays in SortedList; it sets Count back to zero and nulls out the slots so values can be garbage-collected. The capacity stays at whatever it was. If you want to release that memory too, set Capacity = 0 or just let the whole SortedList go out of scope and let the GC reclaim everything.

Both types iterate in ascending key order. That's the central guarantee, and it's why you'd reach for either of them over Dictionary.

The Keys and Values properties return collections of the corresponding component, both in the same sorted-by-key order as the main iteration. They're live views, not copies: if you add a new entry to the dictionary or list, the existing Keys or Values reference reflects it on the next enumeration. Modifying the collection mid-enumeration throws InvalidOperationException, which is the same rule as List<T> and Dictionary<T,U>.

The exact type returned by Keys and Values differs between the two classes. SortedDictionary returns SortedDictionary<TKey, TValue>.KeyCollection and .ValueCollection. SortedList returns IList<TKey> and IList<TValue>, which is a stronger interface because the backing structure is already an indexed array. That means on a SortedList you can write:

These index-based accessors exist on SortedList because the backing storage is already indexable. SortedDictionary has no equivalents because reaching "the i-th element of a tree" requires walking the tree, and exposing that as O(1) would be a lie. You can still walk a SortedDictionary with foreach and a counter if you really need positional access, but it's an awkward pattern, and if you find yourself reaching for it the answer is probably "use SortedList instead."

Enumeration speed itself is one of the more practical differences between the types in real workloads. Enumerating a SortedList is essentially walking two arrays in lockstep, which is extremely cache-friendly. Enumerating a SortedDictionary walks the tree in order, which requires holding a small stack of ancestor pointers and chasing one reference per node. For a million entries, the list enumeration is usually 3-5x faster than the dictionary enumeration. That's a sizable factor if you do it often.

By default, both types use Comparer<TKey>.Default. For string, that's an ordinal, case-sensitive comparison. For int, DateTime, and other numeric or temporal types, it's natural numeric or chronological order. For your own types, default comparison only works if the type implements IComparable<T>.

When the default isn't what you want (case-insensitive keys, descending order, custom rules), you pass an IComparer<TKey> to the constructor. The comparer is stored once and used for every key comparison from then on.

Here's case-insensitive product codes:

The keys keep the original casing that was used at insert time (notice Apple is capitalized as it was inserted), but every comparison treats "apple", "Apple", and "APPLE" as equal. The iteration order is also case-insensitive alphabetical: Apple < bread < MILK under the case-insensitive comparer, even though under ordinal rules MILK (M = 77) would come before bread (b = 98).

A descending-order comparer is a common need too. The simplest way is to wrap the default comparer and flip the sign of the result:

The DescendingDecimal class implements IComparer<decimal> and returns y.CompareTo(x) instead of x.CompareTo(y), which flips the sign of every comparison. Pass an instance to the SortedList constructor and every key comparison from there on follows the descending rule, so iteration yields the largest totals first. The same comparer works against SortedDictionary because both constructors take IComparer<TKey>.

A few rules about custom comparers that bite people. The comparer must be a total order: for any x and y, Compare(x, y) must be the negation of Compare(y, x), transitively consistent, and stable (calling it twice with the same inputs has to return the same result). Returning random values, or having Compare(x, y) > 0 and Compare(y, x) > 0 at the same time, corrupts the structure silently. SortedDictionary may end up with duplicates of what should be the same key, or SortedList may fail to find a key that's clearly there.

The deeper details of writing correct comparers, the full IComparer<T> contract, and the distinction between Comparer<T> and IEqualityComparer<T> get a dedicated treatment in the _IComparer & IEqualityComparer_ lesson. For now, the working examples here cover the common cases, and the takeaway is: pass a comparer to the constructor when the default rule isn't what you want, and make sure the comparer defines a real total order.

One of the main reasons to keep keys sorted is to support range queries: "give me everything with a key between X and Y", or "give me the smallest key greater than X." Neither type exposes range methods directly the way SortedSet<T> does with GetViewBetween, but the sorted iteration makes range queries easy with LINQ.

The loop skips dates below from, sums dates within range, and uses break to stop the moment a date exceeds to. The break works because the iteration is in ascending order: once you see a key past the upper bound, every remaining key is also past it. That's a guarantee Dictionary cannot give you, and it's why "iterate to a stop condition" is a meaningful pattern only on sorted types.

The same loop works against SortedList<DateOnly, decimal> without any changes. The interface is the same and so is the iteration order. The difference, again, is the underlying speed: SortedList will iterate the keys/values arrays sequentially, while SortedDictionary will walk the red-black tree.

For SortedList specifically, you can do better than scanning from the start. Use IndexOfKey (or binary-search reasoning) to jump straight to the lower bound:

The indexed access ordersByDate.Keys[i] is O(1) on SortedList because Keys returns an IList<TKey> backed by the keys array. The same indexed access doesn't exist on SortedDictionary because SortedDictionary<TKey, TValue>.KeyCollection doesn't implement IList<TKey>. For range queries on a SortedDictionary you stick with the foreach-and-break pattern, which is still O(n) over the matching slice but O(log n) to reach the start if you bound the lower end with Keys.FirstOrDefault(k => k >= from).

The sorted-iteration property is also useful for things like "find the next event after time T", which a hash-based dictionary cannot answer in less than O(n).

FirstOrDefault walks the sorted iteration until the predicate is true, then stops. Because the iteration is in ascending order, the first match is the smallest key satisfying the condition, which is "the next delivery on or after today." Without the sorted-by-key property, this query would have to scan the whole collection and compare, then track the minimum. Sorted iteration makes it short-circuit.

The two types overlap enough that you can usually start with either and migrate later. The migration is mechanical because the API is shared. But picking right the first time saves work and lets you communicate intent in the type name.

The rule of thumb is straightforward. Pick SortedDictionary when:

Pick SortedList when:

A small footnote on small sizes: for very small collections (say under 100 entries), the constant factors dominate and SortedList typically wins on every operation, including inserts. The arrays are tiny, the shifts are cheap, and there's no per-node allocation. The cross-over for write-heavy workloads usually sits somewhere between a few hundred and a few thousand entries, depending on key type and hardware. If performance matters at the limit, measure on representative data with a benchmarking tool rather than guessing.

The catalog is a textbook SortedList case: built once, capacity hint set, read often, iterated for display. The active-orders map is a textbook SortedDictionary case: writes coming in steadily, removals as orders complete, ordered iteration for "show me the oldest pending order first."

The other thing to call out: neither type is thread-safe. Concurrent reads are fine, but a single writer concurrent with any reader will corrupt the structure. For concurrent workloads, use ConcurrentDictionary<TKey, TValue> (no ordering) or wrap the sorted type with a lock and accept the throughput cost. Concurrent collections get their own dedicated lesson, _Concurrent Collections_.

Putting it together: a small order-tracking system that needs sorted iteration in two places.

(Output trimmed for brevity, the final two sections produce the obvious "Completing: Order #4002 (MILK x2)" and "Remaining pending: 3" lines.)

The catalog is a SortedList because the data is loaded once and read on every page, where iteration speed matters and inserts are zero. The pending orders are a SortedDictionary because new orders arrive throughout the day and completed orders are removed from the middle of the structure. Both iterate in their natural sorted order: alphabetical for product codes, chronological for placement time. The two types coexist in the same program, used where each one is the better fit.

The "find the oldest pending order" pattern uses foreach ... break on the sorted keys collection because SortedDictionary doesn't expose Keys[0]. On a SortedList you would write pendingOrders.Keys[0] and it would be O(1). The trade-off is back to the same one: faster mutation on SortedDictionary, faster index-based access on SortedList.