How to Sort a C# Dictionary By Key (and when not to!)

Overview

Dictionaries in C# are implemented as a Hash Table, this allows near constant time lookups, but is inherently unsorted.

To do a one-off extract of the data from a dictionary, sorted by key, you can use the OrderBy Linq method as follows:

var sorted = myDictionary.OrderBy(x => x.Key);

This is not going to have the best performance, O(n*log(n)), as it needs to sort all the entries, hence why I said only use it for one-off ordering.

If you need to store the elements of your dictionary in order (because you need to to repeatedly access them in order) then you should consider using a SortedList or a SortedDictionary instead:

var mySortedList = new SortedList<string, int>();
var mySortedDictionary = new SortedDictionary<string, int>();

The name SortedList is misleading and comes from it’s internal implementation (using lists and relying on binary search), it’s still a dictionary in that it maps keys to values. SortedDictionary uses a different implementation again, this time using a tree structure and binary search.

By using these structures you can extract the list of elements in order in linear time O(n), but lose some performance in lookup and insertion times.

One-off sorting dictionary by key and by value

As mentioned in the overview, the Linq OrderBy method can be used to extract the elements of a dictionary and sort them. If you need to do this repeatedly you should consider the SortedList or SortedDictionary data structures below, but for one off sorting it’s ideal. In this section I’ll also show you how to sort a dictionary in descending order and how to sort a dictionary by value, all with example code you can reuse.

Linq OrderBy

OrderBy lets you sort a dictionary by it’s keys, or more accurately, it lets you extract an IOrderedEnumerable of KeyValuePairs from your dictionary.

var fruit = new Dictionary<string, int>
{
    ["apple"] = 1,
    ["pear"] = 4,
    ["banana"] = 6,
};

foreach (var item in fruit.OrderBy(x => x.Key))
{
    Console.WriteLine(item);
}

/* this code outputs:
[apple, 1]
[banana, 6]
[pear, 4]
*/

As mentioned in the overview, the dictionary doesn’t store the elements in order, so sorting them will be O(n*log(n)).

Linq OrderByDescending

There is also the OrderByDescending Linq method, which does as it’s name suggests – it reverses the order:

var fruit = new Dictionary<string, int>
{
    ["apple"] = 1,
    ["pear"] = 4,
    ["banana"] = 6,
};

foreach (var item in fruit.OrderByDescending(x => x.Key))
{
    Console.WriteLine(item);
}

/* this code outputs:
[pear, 4]
[banana, 6]
[apple, 1]
*/

Sort C# Dictionary by Value

To sort a dictionary by value we make use of the same OrderBy method, we just pass is a slightly different lamba expression:

var sorted = myDictionary.OrderBy(x => x.Value);

Or to show this in context:

var fruit = new Dictionary<string, int>
{
    ["apple"] = 1,
    ["pear"] = 4,
    ["banana"] = 6,
};

foreach (var item in fruit.OrderBy(x => x.Value))
{
    Console.WriteLine(item);
}

/* this code outputs:
[apple, 1]
[pear, 4]
[banana, 6]
*/

And of course, you can always sort it descending:

var sorted = myDictionary.OrderByDescending(x => x.Value);

Dictionary Style Data Structures with Sorting Built In

When I say dictionary style, what I mean is they map keys to values as so:

var fruit = new SortedDictionary<string, int>
{
    ["apple"] = 1,
    ["pear"] = 4,
    ["banana"] = 6,
};

Console.WriteLine($"apple's value is: {fruit["apple"]}");

/* this code outputs:
apple's value is: 1
*/

When I say they have sorting built in, I mean they internally store their items in order, so it’s quick and easy O(n) to get the values out in order.

Both the SortList and SortedDictionary have these properties.

C# SortedList

As mentioned above, the name of this data structure can be misleading. It maps keys to values so can be use just like a dictionary.

The name comes from it’s internal implementation using a list. It uses a binary search to find items by key (which is slower than the has table implementation used by Dictionary).

As the name suggests, it stores it’s values in order. So if we iterate through the elements of the SortedList they come back in order:

var fruit = new SortedDictionary<string, int>
{
    ["apple"] = 1,
    ["pear"] = 4,
    ["banana"] = 6,
};

foreach (var item in fruit)
{
    Console.WriteLine(item);
}

/* this code outputs:
[apple, 1]
[banana, 6]
[pear, 4]
*/

The important thing to note here, is that we didn’t use an OrderBy clause on our foreach line. The data is guaranteed to be returned in the order of the keys.

SortedDictionary

The only difference here is its internal implementation (using a tree structure) which can have some slightly different performance trade offs when it comes to lookups and insertions. For our purposes, this works just like a SortedList:

var fruit = new SortedDictionary<string, int>
{
    ["apple"] = 1,
    ["pear"] = 4,
    ["banana"] = 6,
};

foreach (var item in fruit)
{
    Console.WriteLine(item);
}

/* this code outputs:
[apple, 1]
[banana, 6]
[pear, 4]

If you’re trying to decide between the two, consider trying both on a sample of your data and see if you can spot a different. Personally, if there’s no significant performance difference, I use SortedDictionary as I feel the name is less likely to cause confusion.

Linq Reverse

What is the equivalent of OrderByDescending for these data structures? If you want to iterate through the elements of a SortedList or SortedDictionary in reverse order, then the Linq Reverse method is your friend:

var fruit = new SortedDictionary<string, int>
{
    ["apple"] = 1,
    ["pear"] = 4,
    ["banana"] = 6,
};

foreach (var item in fruit.Reverse())
{
    Console.WriteLine(item);
}

/* this code outputs:
[pear, 4]
[banana, 6]
[apple, 1]
*/

Summary

To sort a C# Dictionary by it’s keys as a one off, use OrderBy or OrderByDescending:

var sorted = myDictionary.OrderBy(x => x.Key);
var sorted = myDictionary.OrderByDescending(x => x.Key);

To sort a C# Dictionary by it’s values as a one off, use OrderBy with x => x.Value as the lamba expression:

var sorted = myDictionary.OrderBy(x => x.Value);

If you need a datastructure that still has dictionary style value lookups by key, use either a SortedList or SortedDictionary:

var sortedList = new SortedList<string, int>();
var sortedDict = new SortedDictionary<string, int>();

To loop over these in descending order by key, use the Linq Reverse method:

foreach (var item in sortedList.Reverse()) { ... }

Conclusion

I hope this has cleared up any confusion there might have been around how to Sort a C# Dictionary by it’s keys or it’s values. It might even have brought some new data structures to your attention.

If you want to know more about how these data structures actually perform, leave a comment below and I’ll update this post with some real-world performance benchmarks.

One Reply to “How to Sort a C# Dictionary By Key (and when not to!)”

Leave a Reply

Your email address will not be published. Required fields are marked *