How does C# SortedList internally work?

Question

I was wondering, how does the SortedList work. I know that a regular List is based on a dynamic array, but what is SortedList based on?

And what sorting algorithm it uses?

Thanks

Answer 1

SortedList class source code can be found here.

According to this source, SortedList keeps data in two plain arrays of keys and values:

private TKey[] keys;
private TValue[] values;

Sort order is maintained on the array of keys. When a new item (key/value pair) is added, SortedList first finds proper index in the sorted array of keys (using Array.BinarySearch), then moves partial contents of both key and value arrays (using Array.Copy) starting from this index upward to create a gap where both key and value are inserted. Likewise, when an item is deleted by its key, SortedList searches for the item's index in the array of keys, then moves partial contents of both arrays from this index downward to close the gap.

So, one thing to keep in mind is that when adding to or deleting from a large SortedList, a lot of data may be moved around. On the positive side, retrieving items by index is always fast regardless of the list size.

Answer 2

From the sortedlist documentation: "SortedList is implemented as an array of key/value pairs, sorted by the key."
http://msdn.microsoft.com/en-us/library/e7a8xew6%28v=vs.110%29.aspx

If you use the default constructor (no parameters): "Initializes a new instance of the SortedList class that is empty, has the default initial capacity, and is sorted according to the IComparable interface implemented by each key added to the SortedList object."
http://msdn.microsoft.com/en-us/library/cxb97few%28v=vs.110%29.aspx

Or you can pass a custom comparer:

Initializes a new instance of the SortedList class that is empty, has the default initial capacity, and is sorted according to the specified IComparer interface. http://msdn.microsoft.com/en-us/library/e7a8xew6%28v=vs.110%29.aspx

Other constructor options: http://msdn.microsoft.com/en-us/library/System.Collections.SortedList.SortedList%28v=vs.110%29.aspx

How to use IComparer interface: http://msdn.microsoft.com/en-us/library/system.collections.icomparer%28v=vs.110%29.aspx