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

Catarinacatarrh

can you rephrase this as a question, maybe "Is there any reason c# doesn't have built-in sort and binary search for IList<T>?" right now you are just kinda making a statement and calling on people to vote for this over on microsoft's site, which runs the risk of being closed as spam – Slave

It is kind of hidden in the rambling, but there is a question in there to help me understand why it isn't there if Microsoft intentionally left it out: "Is there some reason they have intentionally omitted this feature?" – Catarinacatarrh

well stack overflow is a question/answer site. it is good etiquette to put more focus on your question (especially in the title of the question). right now it sounds like you've already assumed that this is a bug, and you want others to tell microsoft you agree. better spirit of SO would be to make it clear that the question is "is there a good reason for this or is this a bug?" – Slave

@Kip: I changed the title to a question. Thanks for the suggestion. – Catarinacatarrh

FWIW: meta.stackexchange.com/questions/7211/… – Debut

I was definitely not intending to "abuse" the SO community with this question (or enhancement petition however you look at it), and I apologize if I did. In the future, I will try to make the questions more readily apparent and hold off on any petitions unless there is a lot of feedback that warrants one. – Catarinacatarrh

This isn't a real question. Ask a question, or post this on your blog. – Occlusive

Related: https://mcmap.net/q/964265/-how-do-i-sort-ilist-lt-class-gt – Sisterinlaw

Answer 1

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);

Wernsman

Do you know how they do this under the covers? I assume that since enumerators are usually evaluated only as they are needed (lazy evaluation), then something like a selection sort will be used which would stink since it is O(n^2). – Catarinacatarrh

@Catarinacatarrh - I think the general rule is that LINQ-to-Objects operators are "as lazy as is appropriate for most uses". Given some IEnumerable implementations may be lazy, having OrderBy repeatedly enumerate through the input looking for the successively lower values would be extremely wasteful. That said, if I'm reading things right, it uses EnumerableSorter<T>.QuickSort under the covers, ie. an array-based QuickSort implementation. – Bootless

If you're concerned about whether the sort is immediate or lazy, then instead of list.OrderBy(...), use list.OrderBy(...).ToList(), which will force the sort to take place immediately. – Stigma

@Kyralessa - That is a good suggestion to get around the lazy evaluation, however, it doesn't get around my original concern about having to create a copy of an ILIst<T> to be able to sort it. – Catarinacatarrh

"do you know how they do this under the covers?" They likely allocate an iterator class and it returns the compared items using the orderby function you passed in. – Wernsman

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;
        }

Classic

However, it's important to realize this won't sort the list in place (which might not be a problem). – Mungovan

@lomaxx: How would it create added complexity for those class that implement IList<>? The index get/set properties already exist, and those could simply be used in the static Sort(List<T>) method. – Catarinacatarrh

@dewald: Because it is more code to write, and it does not make sense to sort every type of collection. – Roseliaroselin

sorry, not a C# guy... if there is already a static Sort(List<T>), then i would definitely agree that there is no need to add a sort function to the interface. Java is similar: Collections.sort(List<?>) is the static sort method for any list. – Slave

@Kip: There is an instance method within the List<T> class called Sort(). Jave DOES support what I am asking: static void Collections.sort(List<?>). In Java List<?> is actually an interface. – Catarinacatarrh

He's not asking for a sort member function on the interface, but a static function elsewhere, taking an IList as argument. That wouldn't add complexity for those implementing an IList. – Addington

This is not an inplace sort. Then why not accept IEnumerable and return addresses.OrderBy(x => x).ToList() ? – Sisterinlaw

Answer 3

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.

Odessa

@Marc: Those are nice extension methods, however, I am just surprised that we have to write code to perform these basic operations. Like you said, "IList<T> has a read/write indexer, so it is certainly possible to do both the sort and binary-search without the hack above". In my opinion, these methods should be a part of the framework to prevent each project from having to create its own version. – Catarinacatarrh

Answer 4

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>.

Mungovan

Based on Hallgrim's post at #227481, it seems that using ArrayList.Adapter(IList) with an IList< T > will perform unnecessary copying that I am trying to avoid. – Catarinacatarrh

Answer 5

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.

Griqua

In C#, a "list" generally provides direct element indexing on top of a "collection" that is simply add/remove elements. – Mungovan

You can sort linked lists in O(nlgn) with merge sort. – Sutphin

I'm not actually aware of any implementation of IList<T> that uses linked list as a storage. In particular, the stock LinkedList<T> class does not implement IList<T>. – Awake