Why is there no Sort for IList<T>?!?! (edited)

Question

I was pretty surprised when I discovered that there is no direct way to sort or perform a binary search on an IList< T >. Just like there are static methods to sort and perform a binary search on an Array, I think that it would be awfully helpful to have similar static methods that take an IList< T >.

Currently:

class Array
{
    static Sort<T>(T[] array);
    static int BinarySearch<T>(T[] array, T item);
}

I wish they would add:

class List
{
    static Sort<T>(IList<T> list);
    static int BinarySearch<T>(IList<T> list, T item);
}

I glanced at the .NET Framework 4.0 Beta SDK and there still doesn't appear to be a solution to this problem.

I know that I could work around this by creating an extension method that checks if it is a List< T > and then sort/search using the List< T > instance; however, if it is not an instance of a List< T >, then I have to perform a copy (which stinks for very large lists). I know I could do all of this, but why? Is there some reason they have intentionally omitted this feature?

To try to get this in the .NET 4.0 Framework, I have created a suggestion via Microsoft's Connect program. If you are frustrated like me about this issue, vote on it and maybe it will get added.

https://connect.microsoft.com/VisualStudio/feedback/ViewFeedback.aspx?FeedbackID=474201

Answer 1

You do have ArrayList.Adapter that allows the use of ArrayList's sorting routines, but it would cause a huge performance impact for generic lists of unboxed value types, plus both virtual call and interface dispatch overhead.

For both reference and value types, the interface dispatch could be expensive, meaning a call to ICollection<T>.CopyTo an array T[] followed by separate sort could be the fastest general purpose option, including a custom extension to directly sort on the IList<T> object.

List<T> has a Sort method because it can very efficiently operate on the underlying array of type T[]. There is simply no way to do this for an arbitrary IList<T>.

Answer 2

I think there's a pretty good case for not including a sort method for IList<T>. First, it would create added complexity for those that want to implement an IList and second it would make it harder for the IList interface to conform to the Interface Segregation Principle.

Generally what I do if I need to perform a sort on an IList<T> is create a new List<T> and pass in the IList<T> as a parameter

so for example:

        public IList<Address> SortAddresses(IList<Address> addresses)
        {
            var sortedAddresses = new List<Address>(addresses);
            sortedAddresses.Sort();
            return sortedAddresses;
        }

Answer 3

I'm not a C# expert, but very few List implementations support sorting, binary search, or even indexed retrieval. Lists are generally based on linked lists which don't usually offer an O(1) way of retrieving an item by its index. If you want to locate an element quickly, then use something that keeps the elements in sorted order like a tree or an array as suggested by others.

I do find the fact that IList includes an indexed retrieval method interesting. You might want to consider using SortedList instead of List since it looks like it should support lookups by index or key in O(1) time. In general, if you need something that supports fast lookup, then look for a data structure that keeps its elements in order instead of sorting them explicitly. If nothing else, C# has quite the litany of data structures already.

Answer 4

LINQ has a OrderBy method that works on all IEnumerable<T>, including IList<T>. You can accomplish the same thing using OrderBy.

// Order a list of addresses:
IList<string> list = ...
var orderedList = list.OrderBy(input => input);

Answer 5

The good news is that you can write such methods fairly easily; and thanks to C# 3.0 extension methods, you can make this work on the interface:

public static class ListExt
{
    public static void AddRange<T>(this IList<T> list, IEnumerable<T> items) {
        foreach(T item in items) list.Add(item);
    }
    public static void Sort<T>(this IList<T> list) {
        Sort<T>(list,Comparer<T>.Default); // ordinal sort by default
    }
    public static void Sort<T>(this IList<T> list, IComparer<T> comparer)
    { // very poor implementation!
        List<T> concreteList = new List<T>(list);
        concreteList.Sort(comparer); // cheat!
        list.Clear();
        list.AddRange(concreteList);
    }
    public static int BinarySearch<T>(this IList<T> list, T item) {
        return BinarySearch<T>(list, item, Comparer<T>.Default);
    }
    public static int BinarySearch<T>(this IList<T> list, T item,
        IComparer<T> comparer)
    {...} // TODO
}

Now all that remains is the TODO code itself (and probaby re-write Sort ;-p); but after that:

IList<T> list = ...
list.Sort();
T huntFor = ...
int i = list.BinarySearch(huntFor);

Importantly, IList<T> has a read/write indexer, so it is certainly possible to do both the sort and binary-search without the hack above.

Answer 6

Others have given good methods for sorting an IList<T>. But I'd like to speak to why (in my opinion) IList<T> doesn't have a Sort method.

Methods like Add, Remove, and Insert are fairly simple operations. It's easy to tell what's happening with one of those. But more importantly, it doesn't matter what type of object you're dealing with. You can Add any type of object of type T to your IList and not have to wonder what will happen. Whether it's an IList<Customer>, an IList<Rutabaga>, or an IList<string>, it's obvious that Add will always put a new one on the end; Insert will always put a new one at your specified position; RemoveAt will always remove one from your specified position; etc.

With Sort this isn't true at all. Customers, Rutabagas, and strings may all sort entirely differently. Perhaps Customers sort by LastName, Firstname; Rutabagas sort by ripeness; and strings sort case-sensitively. This makes Sort different from every other operation in IList<T>, because it will behave differently based on the type of T.

You may say: What about Contains(T item) and Remove(T item)? True, those can behave differently depending on what type T is. But there's a clear "default" case for both of those: Matching by object identity. There's no clear default case for sorting. Better to leave it out and let the user specify what kind of sorting he wants, even if that means he can't sort in place.