Difference in sorting between .NET 3.5 and .NET 4.0

Question

I've come across a very weird behaviour of the .NET framework(s), when sorting a collection. This behaviour is different between .NET 3.5 and 4.0 (but I think I know why), but more importantly (and that's my real concern here), the behaviour is different accross different machines on the same framework.

Context

I'm working on a piece of software that's relying on some third party software (spring.net in this case but it doesn't matter), and at some point, it's sorting a collection that has all its item "equal" (the comparer always return 0). This is NOT under my control and I'd be very fine with it if the behaviour of sorting that list was always consistent. It's not.

How to reproduce

Create a simple project, in .NET 3.5, and run the code below. When compiled in 3.5, the behaviour seems to be consistent, and the collection will be "reversed" (it comes out as Three, Two, One). Now, please change the project target to .NET 4 (not 4.5), and run it again: On my machine, it doesn't reverse the collection anymore (One, Two, Three), but on some other colleagues machine, it does (Three, Two, One)!!! We have exactly the same setup...

Can you please tell me, on your machine, under 4.0, which it is? Reversed or not reversed?

I'm trying to assess whether my setup is correct, or not.

Proof of concept

class Program
{
    static void Main()
    {
        var collection = new ArrayList
        {
            "One",
            "Two",
            "Three",
        };

        // It should in any case write One, Two, Three
        Console.Out.WriteLine("Before sort: ");
        foreach (string item in collection)
        {
            Console.Out.WriteLine("\t"+item);
        }

        collection.Sort(new OrderComparator());

        // In .NET 3.5, it will write Three, Two, One
        // In .NET 4, it will sometimes write Three, Two, One, sometimes One, Two, Three: what is it for you?
        Console.Out.WriteLine("After sort: ");
        foreach (string item in collection)
        {
            Console.Out.WriteLine("\t" + item);
        }

        Console.Out.WriteLine("--end--");
        Console.Read();
    }
}

public class OrderComparator : IComparer
{
    public virtual int Compare(object o1, object o2)
    {
        return 0;
    }
}

Also, if you have any idea why this is happening, please let me know!

Answer 1

The sort done by ArrayList.Sort() is not stable, therefore you cannot predict the order in which "identical" items will sort.

Further, because ArrayList.Sort() may use a random mechanism to select the pivot for its QuickSort algorithm, identical items may be sorted differently on different PCs or even on the same PC.

[EDIT: I can't find any evidence for a random pivot being chosen in current implementations, but the array sort is still unstable. I'm guessing the randomness comes from the native code Quicksort implementation in TrySZSort() which is what probably gets called.]

Also for interest's sake, Reflector shows this code in the ArrayList.Sort() (if you dig in a bit):

internal void Sort(int left, int length)
{
    if (BinaryCompatibility.TargetsAtLeast_Desktop_V4_5)
    {
        this.IntrospectiveSort(left, length);
    }
    else
    {
        this.DepthLimitedQuickSort(left, (length + left) - 0x1, 0x20);
    }
}

which seems to be selecting an entirely different sort algorithm for .Net 4.5.