C# faster sorting than SortedList<>

Question

we have a

SortedList<Resource, Resource> resources =
    new SortedList<Resource, Resource>(new ResourceIdle());

that we use in our simulation. This list of resources is initialised in this way because we want to pass different comparers at any point in time. First problem we have is that the SortedList<> requires an extra comparison within the comparer so that we can add different instances of Resource with the same properties. For example if the Comparer looks like:

public int Compare(Resource x, Resource y)  
{  
    int priority1 = x.Priority;    
    int priority2 = y.Priority;    

    if (priority1 > priority2) { 
      return -1;  
    } else if (priority1 < priority2) {  
      return 1;  
    } else {  
      return (x.Id.CompareTo(y.Id));  
    }  
}  

then we have to make the extra comparison when priorities are the same otherwise we get back an exception for an entry with the same key. So my question is, is there another way of achieving this? And as a secondary question is there anything faster than the SortedList<> for ordering large number of objects?

Answer 1

Well, SortedDictionary<,> has different performance characteristics - it depends on what you're doing with it. MSDN has quite a lot of detail comparing the two:

The SortedDictionary<TKey, TValue> generic class is a binary search tree with O(log n) retrieval, where n is the number of elements in the dictionary. In this respect, it is similar to the SortedList<TKey, TValue> generic class. The two classes have similar object models, and both have O(log n) retrieval. Where the two classes differ is in memory use and speed of insertion and removal:

• SortedList<TKey, TValue> uses less memory than SortedDictionary<TKey, TValue>.
• SortedDictionary<TKey, TValue> has faster insertion and removal operations for unsorted data: O(log n) as opposed to O(n) for SortedList<TKey, TValue>.
• If the list is populated all at once from sorted data, SortedList<TKey, TValue> is faster than SortedDictionary<TKey, TValue>.

Answer 2

it is a requirement that the list is always sorted at any time? if not, it would definitely be faster to only sort on demand. another idea is to have the sorting be done by an "OrderPriority" which is a combination of the Priority and ID fields, therefore only one comparison needs to be made:

int OrderPriority { get { return Priority * MAX_ID + ID; } }

this assumes that the IDs do not get too large...