Comparison Method for sorting by float

Question

in my current project i need to sort a List of nodes based on their position, which is represented by two float values. I implemented the IComparable Interface in my Node class and initially used this as the CompareTo method:

public int CompareTo(Node other)
{
    if(y > other.y)
        return 1;
    else if(y < other.y)
        return -1;
    else if(x > other.x)
        return 1;
    else
        return -1;
}

Then I simply called nodeList.Sort(). The idea was that the nodes would be sorted by their Y, and if it was equal they would be sorted by their X instead. This worked well when I tested it with 12 nodes, but after increasing the number of nodes to 21 there suddenly were mistakes in the order of the nodes:

      x       y
 0: 2,089 | 0,048
 1: 1,195 | 0,145
 2: 2,603 | 0,499
 3: 1,750 | 0,750
 4: 0,478 | 0,526
 5: 2,620 | 1,942
 6: 2,868 | 1,473
 7: 2,806 | 0,960
 8: 2,071 | 2,146
 9: 1,452 | 2,119
 ...

I managed to get it working correctly by replacing my CompareTo method with this:

public int CompareTo(Node other)
{
    int comparison = y.CompareTo(other.y);
    if (comparison != 0)
        return comparison;
    else
        return x.CompareTo(other.x);
}

Now it sorts both the list with 12 nodes and the one with 21 nodes correctly.

Another test using this also gives correct results:

public int CompareTo(Node other)
{
    int comparison = Math.Sign(y - other.y);
    if (comparison != 0)
        return comparison;
    else
        return Math.Sign(x - other.x);
}

What I'd like to know is why my first attempt failed after adding more nodes? I did some searching on the comparison of float values, but all I found was that there could be mistakes when checking if two floats were equal, which is not the case here (or is it?).

I can imagine it has something to do with the fact that List.Sort() uses a different algorithm once the list has >16 elements, but I still don't get why my first attempt would do differently than float.CompareTo()?

Answer 1

The original sort function you gave doesn't correctly handle equal values, so a.CompareTo(a) returns -1 instead of the expected 0. This is not the expected behavior of CompareTo(), which should be transitive. The internal implementation of List.Sort() may rely on this transitivity, which would break under your implementation.

If you're interested in trying to dig further into what exactly List.Sort() does under the hood, check out the reference source for ArraySortHelper, which gets called by Array.Sort which gets called by List.Sort. It looks like the algorithm is .NET version dependent, and also uses IntroSort which dynamically switches approaches.