Skip to content
Tutorials Center
My learning

Topics

Lesson 46 of 182 ยท Collections

SortedDictionary, SortedList and Ordering

Learn C# sorted collections - SortedDictionary vs SortedList vs Dictionary, binary search, IComparable and IComparer, custom ordering, and why List.Sort is unstable but OrderBy is stable.

A Dictionary<TKey, TValue> is wonderfully fast, but it makes no promise about the order of its keys. Sometimes the order is the whole point: a leaderboard sorted by score, a calendar of events sorted by date, a price list sorted by product code. For those jobs .NET offers sorted collections, which keep their keys in order all the time, and a whole system of comparison interfaces that tells every sorting tool in the framework what "smaller" and "larger" mean for your types.

This lesson covers SortedDictionary and SortedList, how they differ from the hash-based Dictionary, how to teach your own types to sort with IComparable<T> and IComparer<T>, how binary search works on sorted data, and an important caveat: List<T>.Sort is unstable, while LINQ's OrderBy is stable. It builds on Dictionary and HashSet and SortedSet.

Sorted vs hashed

A hash-based collection finds a key by turning it into a number. A sorted collection finds a key by comparing it with other keys. That single difference explains every trade-off in this lesson.

C# Dictionary vs SortedDictionary

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with Console.ReadLine()), it gets the next line from this box.

Enumerating a SortedDictionary always yields entries ordered by key. With a plain Dictionary you would have to sort the keys yourself every time you wanted to display them.

SortedDictionary: a tree of entries

SortedDictionary<TKey, TValue> stores its entries in a balanced binary search tree (a red-black tree). Adding, removing and looking up a key all cost O(log n), because each step down the tree discards half of the remaining candidates. Memory is allocated per entry, so adding items never copies a big array.

It offers the same members you know from Dictionary: the indexer, Add, TryGetValue, ContainsKey, Remove and Count. It does not offer positional access, and it has no cheap Min/Max properties: Keys.First() works but Keys.Last() walks the whole tree on a SortedDictionary (O(n)), so for repeated "largest key" queries prefer SortedSet<T>.Max or a SortedList.

SortedList: sorted arrays

Despite its name, SortedList<TKey, TValue> is not a list of items. It is a dictionary that stores keys and values in two parallel sorted arrays. Finding a key is a binary search, O(log n). Because the data is contiguous, it uses less memory per entry than a SortedDictionary and it supports index access to keys and values by position.

C# SortedList and positional access

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with Console.ReadLine()), it gets the next line from this box.

GetKeyAtIndex and GetValueAtIndex are recent additions; the older way to write the same thing is events.Keys[2]. The price of the array layout is that inserting or removing a key in the middle shifts the entries after it, which is O(n). Adding keys in already-sorted order, however, appends at the end and is cheap.

Which one should I choose?

Dictionary SortedDictionary SortedList
Lookup O(1) average O(log n) O(log n)
Insert / remove O(1) average O(log n) O(n), O(1) at the end
Enumerate sorted no yes yes
Memory medium highest (node per entry) lowest
Index by position no no yes

A good rule: use Dictionary unless you need order. If you need order and your data is built once (or mostly appended) and then read many times, use SortedList. If you insert and remove at random places all the time, use SortedDictionary.

Teaching a type to sort: IComparable

How does SortedDictionary<string, ...> know that "apple" comes before "pear"? Keys implement IComparable<T>, whose single method CompareTo(other) returns a number: negative if this item sorts before other, zero if equal, positive if it sorts after. All built-in types such as int, string, DateTime and decimal do this already. For your own types, you add it.

C# Implementing IComparable of T

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with Console.ReadLine()), it gets the next line from this box.

Notice that 1.10.0 sorts after 1.2.5. If you had sorted these as strings, "1.10.0" would have come before "1.2.5", because the character 1 is smaller than 2. Comparing fields in the right order, one at a time, avoids that mistake.

Sorting a record or a tuple on several fields is easier with ValueTuple comparison: (Major, Minor, Patch).CompareTo((other.Major, other.Minor, other.Patch)). Tuples compare element by element, left to right, so the one-liner does what the longer method above does.

Your CompareTo must be consistent: if a.CompareTo(b) is negative, then b.CompareTo(a) must be positive, and the relation must be transitive. A sorting algorithm built on a broken comparison can produce a wrong order, loop strangely, or throw InvalidOperationException ("IComparer.Compare() method returns inconsistent results").

Ordering from the outside: IComparer

IComparable<T> gives a type one natural order. But the same people may be sorted by age today and by name tomorrow. IComparer<T> is a separate object with a method Compare(x, y) that defines one particular ordering. Every sorted collection and every sort method accepts one.

C# Custom IComparer and Comparer.Create

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with Console.ReadLine()), it gets the next line from this box.

Look at the last line of output: beta and BETA are the same key under a case-insensitive comparer, so the third assignment replaced the value of the existing entry and left the first spelling of the key in place. The comparer defines both ordering and equality for sorted collections: two keys that compare as zero are the same key.

When you give a sorted collection a comparer, the comparer alone decides what is a duplicate. If your comparer says two different people are equal (for example it compares only ages), then SortedSet<Person> will refuse to add the second person, and SortedDictionary will overwrite the value. Always include a tie-breaker field unless merging is what you want.

Binary search on sorted data

If data is already sorted, you can find an item far faster than by scanning. Binary search looks at the middle item, decides whether the target lies in the left or right half, and repeats on that half. Each step halves the work, so a million sorted items need at most about 20 comparisons. Array.BinarySearch and List<T>.BinarySearch implement it.

C# BinarySearch and its negative result

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with Console.ReadLine()), it gets the next line from this box.

When the item is absent, the method returns a negative number: the bitwise complement (~) of the index where the item would have to be inserted to keep the array sorted. Here ~(-5) is 4, because 30 fits between 23 (index 3) and 42 (index 4). The array must already be sorted with the same comparer; binary search on unsorted data silently gives wrong answers.

Sort stability: List.Sort versus OrderBy

A sort is stable when items that compare as equal keep their original relative order. This matters when you sort in several passes ("by city, then by name") or when the original order carries meaning (arrival time).

Array.Sort and List<T>.Sort use an introspective sort, which is not stable. LINQ's OrderBy and ThenBy are stable. The documentation tells you not to rely on List.Sort being stable, and with longer lists you can see the difference.

C# Unstable Sort vs stable OrderBy

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with Console.ReadLine()), it gets the next line from this box.

The OrderBy line lists the priority-0 jobs in arrival order, as it must. If the List.Sort line differs, that is the instability showing. For lists of 16 items or fewer the underlying algorithm happens to use insertion sort, which is stable, so a small test can hide the problem; real data of any size will show it.

If you need stability with List<T>, either use OrderBy(...).ToList() or add the original index as a final tie-breaker in the comparison. PriorityQueue has the same caveat for equal priorities, covered in Stack, Queue, LinkedList and PriorityQueue.

Sorting performance notes

  • Sorting n items with Array.Sort or List.Sort is O(n log n). Sorting a list once and then using BinarySearch beats a hash lookup only when you also need order.
  • OrderBy allocates a buffer and a key array. For one big sort on a hot path, List.Sort with a comparer is usually faster and allocates less.
  • Pass a static comparer or Comparer<T>.Default rather than creating a lambda in a loop.
  • Sorted collections are slower than hash collections for pure lookup. Do not choose SortedDictionary "just in case" order might be useful.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. What is the main difference between how Dictionary and SortedDictionary find a key?

    Dictionary computes GetHashCode and jumps to a bucket (O(1) average). SortedDictionary walks a balanced tree using comparisons (O(log n)) and so can enumerate in order.
  2. 2. Which collection stores keys and values in two parallel sorted arrays and supports access by position?

    SortedList uses arrays, so it uses less memory and offers GetKeyAtIndex, but inserting in the middle is O(n).
  3. 3. Array.BinarySearch returns -5 for a missing value in an array. Where would the value belong?

    A negative result is the bitwise complement of the insertion index, so ~(-5) is 4.
  4. 4. What does IComparable<T>.CompareTo return when the current item should sort after the other?

    Negative means before, zero means equal, positive means after.
  5. 5. You need to sort a list by city and keep the arrival order inside each city. What is the safe choice?

    List.Sort is not guaranteed stable. OrderBy is stable, and an explicit tie-breaker makes any sort deterministic.

Summary

  • SortedDictionary (tree, O(log n) for everything) and SortedList (parallel arrays, O(n) middle inserts, indexable) keep keys in order; Dictionary is faster when you do not need order.
  • IComparable<T>.CompareTo gives a type its natural order: negative before, zero equal, positive after.
  • IComparer<T> (or Comparer<T>.Create) defines an alternative order and is accepted by sorts and sorted collections.
  • In sorted collections the comparer also decides equality; two keys that compare as zero are the same key.
  • BinarySearch needs sorted input and returns the bitwise complement of the insertion point when the item is missing.
  • List<T>.Sort is unstable; OrderBy/ThenBy are stable.

Next: Collection Expressions and Spread