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

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-so开发者_Python百科rt my collection by Name so that the new item appears in the correct place in the list?

---

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.

---

Since your collection is already sorted, just Insert the new item at the appropriate location which you can discover with a binary search. Unfortunately there is not a built-in binary search on IList<T> but you can easily make an extension method that does the job. Be careful when you implement binary search that you do not introduce a classic bug (the bug is a possible overflow in computing the average of the low and high indexes as low + high might overflow). You could use List<T>.BinarySearch as a template.

---

Follow @JonSkeet answer, I made the BinarySearch extension of IList, similar to .NET sourcecode:

public static class IListBinarySearchHelper {
    public static int BinarySearch<T>(this IList<T> source, int index, int count, T item, IComparer<T> comparer) {
        if (index < 0) throw new Exception("Need non negative number of index.");
        if (count < 0) throw new Exception("Need non negative number of count.");
        if (source.Count - index < count) throw new Exception("Invalid offset length of count.");
        Contract.Ensures(Contract.Result<int>() <= index + count);
        Contract.EndContractBlock();

        return Array.BinarySearch<T>(source.Cast<T>().ToArray(), index, count, item, comparer);
    }

    public static int BinarySearch<T>(this IList<T> source, T item) {
        Contract.Ensures(Contract.Result<int>() <= source.Count);
        return BinarySearch(source, 0, source.Count, item, null);
    }

    public static int BinarySearch<T>(this IList<T> source, T item, IComparer<T> comparer) {
        Contract.Ensures(Contract.Result<int>() <= source.Count);
        return BinarySearch(source, 0, source.Count, item, comparer);
    }
}

So now we can do:

var nums = new ObservableCollection<int>();
nums.Add(1);
nums.Add(3);
nums.Add(8);

var result = nums.BinarySearch(1);   /// return 0
result = nums.BinarySearch(4);       /// return -3

This works perfect to me.

The return value follow same rule with Array.BinarySearch, positive number for the found index, negative number for the hint of insertion point.

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?

To answer the question, just insert the value at the point related to BinarySearch return value.