C# SortedList Usage: Sorting Key-Value Pairs Efficiently

When you need to keep key-value pairs sorted by key and also access them by index, SortedList<TKey, TValue> is a practical choice. This article covers c# sortedlist usage in realistic scenarios: how to create and populate the collection, how to read and modify entries, how iteration behaves, and where its performance characteristics fit compared to alternatives like SortedDictionary<TKey, TValue>.

The SortedList Type and Its Place in .NET Collections

SortedList<TKey, TValue> is a generic collection that maintains key-value pairs in ascending key order. It is part of System.Collections.Generic and is backed by two parallel arrays: one for keys and one for values. This backing structure gives it a unique combination of features: sorted enumeration, indexed access, and predictable memory usage.

The non-generic SortedList also exists in System.Collections, but modern code should prefer the generic version to avoid boxing and type casts. The generic version is available in .NET Framework 2.0 and all later versions, including .NET Core and .NET 5+.

A common misconception is that SortedList and SortedDictionary are interchangeable. They both keep keys sorted, but they use different internal structures. SortedList uses arrays, while SortedDictionary uses a binary search tree. That difference matters for insertion and deletion performance, as explained later.

Creating and Populating a SortedList

You instantiate a SortedList<TKey, TValue> by specifying the key and value types. The key type must implement IComparable<T> or you must provide a custom IComparer<T> in the constructor.

var scores = new SortedList<string, int>();

scores.Add("Alice", 85);
scores.Add("Bob", 92);
scores.Add("Carol", 78);

After these additions, the list is internally sorted by key using the default string comparer. You can also initialize it with a capacity to reduce reallocation overhead when you know the approximate size:

var scores = new SortedList<string, int>(10);

If you need a custom sort order, pass an IComparer<TKey>:

var reverseScores = new SortedList<string, int>(Comparer<string>.Create((a, b) => b.CompareTo(a)));

The Add method throws ArgumentException if the key already exists. If you want to insert or update without that exception, use the indexer as shown in the next section.

Reading and Updating Entries

The indexer provides direct access by key. It returns the value for an existing key and sets a new value or adds a new entry when the key is not present.

scores["Bob"] = 95;      // updates existing entry
scores["Dave"] = 88;     // adds new entry

To check whether a key exists without catching exceptions, use ContainsKey or TryGetValue:

if (scores.TryGetValue("Alice", out int aliceScore))
{
    Console.WriteLine($"Alice scored {aliceScore}");
}

TryGetValue is efficient because it performs a single binary search. In contrast, calling ContainsKey followed by the indexer would perform two searches.

Removing entries is straightforward with Remove or RemoveAt:

scores.Remove("Carol");          // by key
scores.RemoveAt(0);               // by index, removes the first (lowest key)

RemoveAt is unique to SortedList; SortedDictionary does not offer indexed removal. This makes SortedList useful when you need to remove the smallest or largest entry quickly.

Iteration and Ordering Behavior

Enumerating a SortedList<TKey, TValue> yields KeyValuePair<TKey, TValue> objects in ascending key order. This is guaranteed because the internal arrays are always kept sorted.

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

You can also iterate over just the keys or just the values using the Keys and Values properties. These return IList<TKey> and IList<TValue> respectively, which means you can access them by index.

string firstKey = scores.Keys[0];
int lastValue = scores.Values[scores.Count - 1];

This indexed access is a significant advantage over SortedDictionary, which only exposes collections that are not indexable. If your algorithm needs to frequently retrieve the k-th smallest key, SortedList is the natural fit.

Performance and Memory Characteristics

The internal array implementation determines the performance profile. Insertion and deletion are O(n) in the worst case because shifting elements in the array may be required. Lookup by key is O(log n) using binary search. Indexed access is O(1).

For example, adding a key that belongs in the middle of the list forces all subsequent keys to shift one position. This is different from SortedDictionary, where insertion and deletion are O(log n) regardless of position, but lookup is also O(log n) and there is no indexed access.

Memory usage also differs. SortedList stores keys and values in contiguous arrays, which reduces overhead per entry but may waste space if the capacity exceeds the count. SortedDictionary uses a tree with nodes, which has higher per-entry overhead but no preallocated capacity.

In practice, use SortedList when you have a relatively static set of data that you need to sort once and then read frequently, especially if you need index-based access. Use SortedDictionary when you have many insertions and deletions and do not need indexed access.

SortedList vs SortedDictionary: How to Choose

The decision between the two sorted collections depends on your workload. The table below summarizes the key differences.

Use SortedList when the collection is built once and then read often, or when you need to access elements by index. Use SortedDictionary when you frequently insert and delete elements in arbitrary order and do not need indexed access.

Thread Safety and Concurrent Access

Neither SortedList<TKey, TValue> nor SortedDictionary<TKey, TValue> is thread-safe for concurrent writes. If multiple threads modify the collection simultaneously, you must synchronize access using a lock or use a concurrent collection.

.NET provides ConcurrentDictionary<TKey, TValue> but it does not maintain sorted order. If you need a thread-safe sorted collection, you have to wrap SortedList with your own synchronization or use ReaderWriterLockSlim to allow concurrent reads while writes are exclusive.

A simple approach is to use a lock around all operations:

private readonly object _lock = new object();
private SortedList<string, int> _sorted = new SortedList<string, int>();

public void Add(string key, int value)
{
    lock (_lock)
    {
        _sorted.Add(key, value);
    }
}

For read-heavy scenarios, ReaderWriterLockSlim can improve concurrency, but it adds complexity. Evaluate whether the sorted order is truly necessary before introducing this overhead.

Practical Example: Caching with SortedList

A common use case for SortedList is a simple cache that expires entries by time. Suppose you want to store timestamps as keys and cached objects as values. Because SortedList keeps keys sorted, you can easily remove entries older than a certain threshold.

public class TimestampCache<TValue>
{
    private readonly SortedList<DateTime, TValue> _items = new SortedList<DateTime, TValue>();

    public void Add(DateTime timestamp, TValue value)
    {
        _items[timestamp] = value;
    }

    public void RemoveOlderThan(DateTime cutoff)
    {
        while (_items.Count > 0 && _items.Keys[0] < cutoff)
        {
            _items.RemoveAt(0);
        }
    }

    public TValue GetLatest()
    {
        if (_items.Count == 0)
            throw new InvalidOperationException("Cache is empty.");
        return _items.Values[_items.Count - 1];
    }
}

In this example, RemoveOlderThan repeatedly removes the first entry, which is the smallest timestamp. Each removal is O(n) because of array shifting, but if the cache is small or removals are infrequent, the simplicity and indexed access outweigh the cost. For a high-throughput cache, a SortedDictionary with a separate index might be more appropriate, but it would lose the O(1) access to the oldest entry.

This pattern demonstrates how the unique indexed access of SortedList enables algorithms that are awkward with other sorted collections. When you need both sorted order and index-based retrieval, SortedList is the right tool, provided you understand its O(n) insertion cost and choose it for workloads that are read-heavy or have infrequent writes.