Most efficient way of sorting ObservableCollection<T> with a new item in it

Question

I have ViewModel class as follows:

public class ListViewModel
{
    public ObservableCollection<InfoItem> List { get; set; }
}

public interface InfoItem
{
  int Reference { get; }
  string Name { get; }
}

The collection is sorted by Name which is being displayed in the UI. I have a scenario where the collection contains a couple of thousand items and I add a new item to the collection.

What is the most efficient way to re-sort my collection by Name so that the new item appears in the correct place in the list?

Answer 1

If your collection is sorted already, then perform a binary search on it to find out where you should insert the new item, and then call Insert. Adding the item to the end and then resorting the whole collection would be very wasteful.

It's a shame there isn't a general-purpose BinarySearch extension method on IList<T>, but it shouldn't be too hard to write. Assuming you'd want to write a generic method to do this (which I'd suggest you do - it won't be significantly harder than writing an InfoItem-specific one) you'd either want to take an IComparer<T> or a projection, e.g.

public static int BinarySearch<T>(this IList<T> source, IComparer<T> comparer)

or

public static int BinarySearch<TSource, TKey>(
    this IList<TSource> source,
    Func<TSource, TKey> keySelector)

I suggest you make the return value follow the convention from List<T>.BinarySearch, such that if a match is not found, it returns the bitwise negation of the index where the item would be inserted.