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

Try to aggregate insertions into batches, and sort only at the end of each batch.

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

Answer 3

The BinarySearch method is fast and it was a good plan to try to use this method instead of sorting after every insert. However your plan fails when you actually make the insert because the items in a List<T> are stored consecutively in memory so when you want to insert a new item the existing items must be moved. This means that overall you have an O(n^2) algorithm.

An alternative is to use a SortedList<T, int> where the second parameter is a count so the first time you insert an item the count is one, and the second time you insert the same item you increase the count instead of inserting it a second time.

Related question

• Is there a non-unique-key sorted list generic collection in C#?

Answer 4

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 you're 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.