Frequent inserts into sorted collection

Question

I have sorted collection (List) and I need to keep it sorted at all times.

I am currently using List.BinarySearch on my collection and then insert element in right place. I have also tried sorting list after every insertion but the performance in unacceptable.

Is there a solution that will give better performance? Maybe I should use other collection.

(I am aware of SortedList but it is restricted to unique keys)

Answer 1

PowerCollections has an OrderedBag type which may be good for what you need. From the docs

Inserting, deleting, and looking up an an element all are done in log(N) + M time, where N is the number of keys in the tree, and M is the current number of copies of the element being handled.

However, for the .NET 3.5 built in types, using List.BinarySearch and inserting each item into the correct place is a good start - but that uses an Array internally so your performance will drop due to all the copying you're doing when you insert.

If you can group your inserts into batches that will improve things, but unless you can get down to only a single sort operation after all your inserting you're probably better off using OrderedBag from PowerCollections if you can.

Answer 2

If you're using .Net 4, you can use a SortedSet<T>

http://msdn.microsoft.com/en-us/library/dd412070.aspx

For .Net 3.5 and lower, see if a SortedList<TKey,TValue> works for you.

http://msdn.microsoft.com/en-us/library/ms132319.aspx