Wait, if they both keep keys sorted, why are there two different classes?

This is the first thing everyone asks. On the surface, SortedList<TKey, TValue> and SortedDictionary<TKey, TValue> look identical. They both store key-value pairs and keep the keys sorted. But under the hood, they are completely different animals.

SortedList uses two arrays. One for keys, one for values. Because it's array-based, it's very memory-efficient and extremely fast for looking up a value if you already have the key. However, inserting a new item is expensive because it might have to shift thousands of elements over to make room in the middle of the array to maintain the sort order.

SortedDictionary uses a binary search tree. It doesn't need to shift elements; it just creates a new node and links it. This makes insertions and removals much faster, but it uses more memory per item and is slightly slower for lookups.

I usually follow this rule of thumb: if you're loading a set of data once and then reading from it constantly, go with SortedList. If you're constantly adding and removing items while the app is running, SortedDictionary is your best bet.

Can I change how they decide what "sorted" means?

Yes, and you'll likely need to. By default, these classes use the default comparer for the type you're using. If you're using int or string, it's alphabetical or numerical. But what if you have a custom User object as a key and you want to sort them by their JoinDate?

You can pass an IComparer<TKey> into the constructor. Here is how I'd handle a scenario where I want a list of high scores sorted in descending order (highest score first), which isn't the default behavior.

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

// Usage
var highScores = new SortedDictionary<int, string>(new DescendingIntComparer());
highScores.Add(1500, "Alice");
highScores.Add(2000, "Bob");
highScores.Add(1200, "Charlie");

foreach (var entry in highScores)
{
    Console.WriteLine($"{entry.Key}: {entry.Value}");
    // Outputs: 2000: Bob, 1500: Alice, 1200: Charlie
}

Do these classes allow duplicate keys?

Short answer: No. Neither of them does. Both SortedList and SortedDictionary require unique keys. If you try to Add() a key that already exists, C# will throw an ArgumentException.

If you need to store multiple values for the same key while keeping them sorted, you have to change your value type to a collection. For example, instead of a SortedList<int, string>, you'd use a SortedList<int, List<string>>. It's a bit more boilerplate to manage the inner list, but it's the standard way to handle "one-to-many" sorted relationships.

📋 Practical Task

Build a Chronological Log Viewer

You are building a system that tracks server events. Each event has a DateTime (the timestamp) and a string (the log message). Because logs are generated out of order across different threads, you need to store them in a way that they are always sorted by time regardless of when they were added to the collection.

Your Task:

• Create a program that uses either a SortedList or SortedDictionary to store logs.
• Insert at least four logs with timestamps that are not in chronological order (e.g., add a log from 10:00 AM, then 8:00 AM, then 11:00 AM).
• Write a loop that iterates through the collection and prints the logs to the console.
• Verify that the output is printed in the correct chronological order, regardless of the order in which you called the Add method.