What is the best way to sort an IList<T> in .Net 2.0?

Question

I have an IList<T> that I need to sort, and I would rather not copy the list if possible. I've noticed that ArrayList has an Adapter static method that wraps the passed list without copying it, but this takes an IList and I have an IList<T>. Is it safe to cast from a System.Collections.Generic.IList<T> to a System.Collections.IList and just use the Adapter method?

Note that this is .Net 2.0, so LINQ is not an option.

Answer 1

From the blog of Paul Fox, I recommend the post "How to sort an IList": http://foxsys.blogspot.com/2007/06/how-to-sort-generic-ilist.html

Just in case that blog goes away in the future, I'll copy the post here:

---

How to sort a generic IList

Update

You can read and updated post about sorting generic IList and List. Many people will prefer the methods mentioned in the updated post.

Sorting a generic IList

I was trying to sort a generic IList<> and found a fairly simple way of doing it.

Step 1

You need to implement IComparable for the type contained in your IList. For this example I am going to use a simple Language Dto class.

public class LanguageDto : IComparable {
 private String name;
 public string Name { get { return name; } set { name = value; } }

 public LanguageDto(string name) {
     this.name = name;
 }

 #region IComparable Members
 public int CompareTo(object obj) {
     if (obj is LanguageDto) {
     LanguageDto language = (LanguageDto)obj;
     return this.name.CompareTo(language.name);
     }
     throw new ArgumentException(string.Format("Cannot compare a LanguageDto to an {0}", obj.GetType().ToString()));
 }
 #endregion
}

STEP 2

Sort your IList. To do this you will use the ArrayList.Adapter() method passing in your IList, and then calling the Sort method. Like so...

ArrayList.Adapter((IList)languages).Sort();

Note: languages is of type "IList"

Languages should then be a sorted list of your type!

Answer 2

You cannot cast IList(T) to IList.

After some sniffing with Reflector, it seems like ArrayList.Adapter(IList).Sort() will first copy the list to an object array, sort the array and then copy the array back to a list:

object[] array = new object[count];
this.CopyTo(index, array, 0, count);
Array.Sort(array, 0, count, comparer);
for (int i = 0; i < count; i++)
{
    this._list[i + index] = array[i];
}

You might get boxing overhead if T in your List(T) a value type.

If you need to alter the sequence of the objects in the list that you have, you can do it similarly:

IList<object> unsorted = ...
List<object> sorted = new List<object>(unsorted);
sorted.Sort(); 
for (int i = 0; i < unsorted.Countt; i++)
{
    unsorted[i] = sorted[i];
}

If the list is so huge (as in hundreds of million items) that you cannot make an extra copy in memory, I suggest using a List(T) in the first place or implement your favorite in-place sorting algorithm.

Answer 3

Since the Sort method isn't on the IList interface you might consider creating your own:

interface ISortableList<T> : IList<T>
{
    void Sort();
    void Sort(IComparer<T> comparer);
}

class SortableList<T> : List<T>, ISortableList<T> { }

/* usage */
void Example(ISortedList<T> list)
{
    list.Sort();
    list.Sort(new MyCustomerComparer());
}

In general the parameter type you specify in your method should be the lowest common denominator of members you actually need to call. If you really need to call the Sort() method then your parameter should have that member defined. Otherwise you should probably load it into another object that can do what you want such as:

void Example(IList<T> list)
{
    list = new List<T>(list).Sort();
}

This should actually be pretty fast, almost certainly faster still than writing your own custom inline sort algorithm.