How to sort a dynamic array of heterogeneous numbers?

Question

I want to sort an array that can contain different numeric types (double, float, etc.).This code raises a System.ArgumentException ("Value is not a System.Single") error:

new dynamic[] { 5L, 4D, 3F, 2U, 1M, 0UL }.ToList().Sort();

I know I can use LINQ to do this:

new dynamic[] { 5L, 4D, 3F, 2U, 1M, 0UL }.ToList().OrderBy(x => (decimal)x).ToArray();

But is there a faster way that doesn't involve going through any having to cast each element?

Addendum: I would also like to be able to handle nulls in the list, so even the LINQ query's cast won't help.

Answer 1

First, remove the ToList(). This operation is not required, so just remove it. That will speed up the thing a little bit.

For the rest: No there is no faster way. If first posted an answer with code showing a performance increase with a factor of 2. But, when I ran than code with larger arrays, it became relatively slower and at a point even slower than the original code.

Why? The whole OrderBy is seperated into 2 parts: The generation of keys and the sorting of the values by comparing those keys. If the numbers of items in the array grows, the generation of keys growns lineairly, but the number of compare-operations grows exponentially.

My code did not required all values to be converted to decimals (speed increase during key generation), but during the sorting fase the values needed to unbox which is a performance decredation. With larger arrays, the number of compare operations grew exponentialy, so the number of unboxing grew, which in the end was the sand in the weels.

I've tried other solution likes creating delegates accepting two types of numbers and in that delegate a dynamic piece of compiled code with the optimum comparing solution for both types, which always involves that sometimes a number had to be converted. And during the sorting-fase, this becomes killing.

So simply put: No, your routine cannot be made faster. It does not matter how much time the key-generation-fase, as long as the compare-fase is as fast as possible.

For people who are interested, te original code from my previous answer (which is NOT faster with larger arrays):

    static private dynamic[] testSet = new dynamic[] { 5L, 4D, 3F, null, 2U, 1M, null, 0UL };

    static void Main(string[] args)
    {
        Stopwatch st1 = new Stopwatch();
        st1.Start();
        for(int i = 0; i < 100000; i++)
            Test1();
        st1.Stop();

        Stopwatch st2 = new Stopwatch();
        st2.Start();
        for(int i = 0; i < 100000; i++)
            Test2();
        st2.Stop();
    }

    static public void Test1()
    {
        var result = testSet.OrderBy(x => x == null ? (decimal?)null : (decimal)x).ToArray();
    }

    static public void Test2()
    {
        var result = testSet.OrderBy(x => (object)x, new HeterogeneousNumbersComparer()).ToArray();
    }

    public class HeterogeneousNumbersComparer : IComparer<object>
    {
        public int Compare(object a, object b)
        {
            if (a == null)
                if (b == null)
                    return 0;
                else
                    return -1;
            else if (b == null)
                return +1;

            if (a.GetType() == b.GetType())
            {
                switch(Type.GetTypeCode(a.GetType()))
                {
                    case TypeCode.Byte:
                        return ((Byte)a).CompareTo((Byte)b);
                    case TypeCode.Decimal:
                        return ((Decimal)a).CompareTo((Decimal)b);
                    case TypeCode.Double:
                        return ((Double)a).CompareTo((Double)b);
                    case TypeCode.Int16:
                        return ((Int16)a).CompareTo((Int16)b);
                    case TypeCode.Int32:
                        return ((Int32)a).CompareTo((Int32)b);
                    case TypeCode.Int64:
                        return ((Int64)a).CompareTo((Int64)b);
                    case TypeCode.SByte:
                        return ((SByte)a).CompareTo((SByte)b);
                    case TypeCode.Single:
                        return ((Single)a).CompareTo((Single)b);
                    case TypeCode.UInt16:
                        return ((UInt16)a).CompareTo((UInt16)b);
                    case TypeCode.UInt32:
                        return ((UInt32)a).CompareTo((UInt32)b);
                    case TypeCode.UInt64:
                        return ((UInt64)a).CompareTo((UInt64)b);
                }
            }
            return Convert.ToDecimal(a).CompareTo(Convert.ToDecimal(b));
        }
    }
}

The numbers (on my machine are):
Test1: 550ms
Test2: 263ms
So... a factor 2!!!