.NET – Sorted Collections

Beyond exploring .NET’s Sorted Collections, I’d like to share a related anecdote. Some failures stick with you, and this one is no exception. It’s the story of an interview I bombed—not because I misunderstood the problem, but because I missed one small yet critical detail: how to work with sorted collections in C#.

During the interview, everything seemed to be going smoothly. I was given a coding exercise that wasn’t particularly challenging. The task required me to implement a data processing algorithm based on a set of requirements and return the result as a SortedList. Simple enough, right?

I wrote the code, implemented the processing logic, and ran it. The tests failed. I double-checked the logic—it was correct. I ran it again, but still no luck. Although I was producing the correct output, the code sandbox used by the interviewer expected the results in a SortedList.

At that moment, without knowing the type’s interface, and with no IntelliSense or help from the web, I did my best to create and format the result—but without success. I left the interview frustrated, knowing I had come so close. 🤦‍♂️

After that experience, I made it a point to understand the SortedList. That’s what led to this post—here’s what I’ve learned about C#’s sorted collections and how they can save you both time and interviews!

1. SortedList

A SortedList is essentially a dictionary that keeps its keys in sorted order.

• When to Use:
  When you need fast lookups (via keys) and guaranteed sorting, especially for smaller datasets.
• Performance:
  Fast lookups, but slower insertions as it has to reorder elements every time a new key-value pair is added.

var sortedList = new SortedList<int, string>();
sortedList.Add(3, "Three");
sortedList.Add(1, "One");
sortedList.Add(2, "Two");

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

Output:

1: One  
2: Two  
3: Three  

2. SortedDictionary

A SortedDictionary is similar to SortedList, but it is optimized for faster inserts and deletions using a Red-Black Tree under the hood.

• When to Use:
  Best for larger datasets that require frequent updates (inserts/removals).
• Performance:
  Logarithmic time complexity for inserts, lookups, and deletions.

Example:

var sortedDict = new SortedDictionary<string, int>();
sortedDict.Add("apple", 10);
sortedDict.Add("banana", 5);
sortedDict.Add("grape", 8);

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

Output:

apple: 10  
banana: 5  
grape: 8  

3. SortedSet

A SortedSet is a collection that holds unique elements in a sorted order. It’s ideal for scenarios where you want sorted data without duplicates.

• When to Use:
  Use it when you need both uniqueness and order.
• Performance:
  Logarithmic time for inserts, lookups, and deletions.

Example:

var sortedSet = new SortedSet<int> { 5, 3, 8, 1, 3 };
foreach (var item in sortedSet)
{
    Console.WriteLine(item);
}

Output:

1  
3  
5  
8  

Key Differences and When to Use Each

Looking back, that interview was a humbling experience. It made me realize that it’s not enough to know how to solve a problem—you also need to be familiar with the right tools to solve it efficiently. I was so close to succeeding, but missing the knowledge of sorted collections made me stumble.

Thank you for reading, and I hope this post prepares you to ace your next interview or build more efficient C# applications. Remember: every setback is an opportunity to grow.