Why does List<T>.Sort() where T:IComparable<T> produce a different order than List<T>.Sort(IComparer<T>)?

MineR 0
Viewed 43

List<T>.Sort() where T:IComparable<T> produces a different order than List<T>.Sort(IComparer<T>), with equal inputs.

Note the comparer is not really correct - it does not return 0 for equality.

Both orders are valid (because the difference lies in the equal elements), but I'm wondering where the difference arises from, having looked through the source, and if it is possible to alter the IComparable.CompareTo to match the behavior of the IComparer.Compare when passed into the list.

The reason I'm looking at this is because IComparable is far faster than using an IComparer (which I'm guessing is why there are two different implementations in .NET), and I was hoping to improve the performance of an open source library by switching the IComparer to IComparable.

A full example is at: https://dotnetfiddle.net/b7s6my

Here's the class/comparer:

public class Point : IComparable<Point>
{
   public int X { get; }
   public int Y { get; }
   public int UID { get; set; } //Set by outside code
    
   public Point(int x, int y)
   {
      X = x;
      Y = y;
   }
    
   public int CompareTo(Point b)
   {
      return PointComparer.Default.Compare(this, b);
   }
}
public class PointComparer : IComparer<Point>
{
   public readonly static PointComparer Default = new PointComparer();
                
   public int Compare(Point a, Point b)
   {
       if (a.Y == b.Y)
       {
          return (a.X < b.X) ? -1 : 1;
       }
       return (a.Y > b.Y) ? -1 : 1;
   }
}

Note the comparer is not mine (so I can't really change it) - and changing the sort order causes the surrounding code to fail.

sorting list c#
1 Answers

As mentioned in comments problem is with IComparer<Point>, which for two equal objects a and b (ones that have same X and Y) returns Compare(a, b) = 1, and Compare(b, a) = 1.

However, question arose why are the sorts still different.

Checking source of ArraySortHelper (see comment of @Sweeper) showed two versions of quick sort algorithm implementations (one of explicit IComparer and one for implicit).

Algorithms are mostly the same, however, function PickPivotAndPartition is a bit different. One function is PickPivotAndParition(Span<T> keys), another is PickPivotAndPartition(Span<T> keys, Comparison<T> comparer).

In first function there's line:

while (... && GreaterThan(ref pivot, ref leftRef = ref Unsafe.Add(ref leftRef, 1))) ;

And in second function similar line looks like:

while (comparer(keys[++left], pivot) < 0) ;

So, that looks to be a point - first function line can be thought as Compare(pivot, left) > 0, while second line as Compare(left, pivot) < 0, so when you have Compare(left, pivot) = 1 and Compare(pivot, left) = 1, condition in first function will be true, while in second - false.

This means that two algorithm implementations can select different array slices and hence have different output.

Quercus0
Related