Perhaps there is such a list in the .NET framework, but I havn't been able to find it yet.
Sure, there is the SortedList, but thats a Key/Value-style hashtable where it sorts on the keys. Sometimes thats fine, but most often I find that it's pretty useless. Especially since you can't have duplicate keys. You can also use the .Sort() method on an ordinary list of course. But what if you need to have a list that's always sorted, e.g. when you Add a new item to the list it's inserted in a sorted manner?! Calling .Sort() after each .Add() isn't really an option since it's way too slow.
So, as you might have expected, when I had the problem again this weekend I ended up writing my own implementation of a SortList.
It might not be pretty, but it seems to work and compared to the .Add();.Sort() alternative it's pretty darn fast :-)
public class SortList<T> : List<T>
where T : IComparable<T>
public new void Add(T Item)
//No list items
//Bigger than Max
int min = 0;
int max = Count-1;
//Find half point
int half = min + ((max - min) / 2);
//Compare if it's bigger or smaller than the current item.
int comp = Item.CompareTo(this[half]);
if (comp == 0)
//Item is equal to half point
else if (comp < 0) max = half; //Item is smaller
else min = half; //Item is bigger
else Insert(min + 1, Item);
The code is based on a standard generic list, and it simply replaces the Add() method with a method that inserts item sorted. It does this by narrowing in on the list, always diving the list in two - much like one would solve the classical game of "Guess the number I'm thinking of".
To test it, I wrote a small test application, that generated an array with 10.000 random integers (values between 0 and 10.000). Then it timed how long it would take to add them to the SortList, and afterwards how long time it would take to Add+Sort them in a usual list (with Sort being called for each Add, cause we need a constantly sorted list).
On my workstation, SortList took about 40 ms to complete the task while List.Add+List.Sort took 2654 ms.
And in case you're wondering, the answer is Yes. The sorted contents was the same in both lists afterwards.