Introduction

When you use OrderBy in LINQ-to-Objects and provide a custom IComparer<T>, you may notice that the comparer is called with the same item on both sides — Compare(x, x) returns 0. This is not a bug. It happens because LINQ's internal sorting algorithm (an introspective sort variant) naturally compares elements with themselves as part of its partitioning and pivot selection logic. Understanding this behavior helps you write correct custom comparers and debug unexpected sorting results.

Observing Self-Comparisons

1using System;
2using System.Collections.Generic;
3using System.Linq;
4
5class LoggingComparer : IComparer<int>
6{
7    public int Compare(int x, int y)
8    {
9        Console.WriteLine($"Compare({x}, {y})");
10        return x.CompareTo(y);
11    }
12}
13
14var numbers = new[] { 3, 1, 4, 1, 5 };
15var sorted = numbers.OrderBy(n => n, new LoggingComparer()).ToList();
16
17// Output includes lines like:
18// Compare(3, 3)   <-- self-comparison
19// Compare(1, 3)
20// Compare(4, 3)
21// Compare(1, 1)   <-- self-comparison
22// ...

The Compare(3, 3) calls happen during the sorting algorithm's pivot comparisons and boundary checks.

Why the Algorithm Does This

LINQ-to-Objects uses a variant of quicksort internally. The .NET runtime implementation in EnumerableSorter<TElement> uses a quicksort that compares the pivot element against all elements in the partition — including itself:

1// Simplified pseudocode of LINQ's internal sort
2void QuickSort(int[] keys, int lo, int hi)
3{
4    while (lo < hi)
5    {
6        int pivot = keys[lo + (hi - lo) / 2];
7        int i = lo, j = hi;
8
9        while (i <= j)
10        {
11            // These loops may compare keys[i] or keys[j] to pivot
12            // when i or j equals the pivot index — self-comparison
13            while (Compare(keys[i], pivot) < 0) i++;
14            while (Compare(keys[j], pivot) > 0) j--;
15
16            if (i <= j)
17            {
18                Swap(keys, i, j);
19                i++;
20                j--;
21            }
22        }
23
24        // Recurse on smaller partition
25        if (j - lo <= hi - i)
26        {
27            QuickSort(keys, lo, j);
28            lo = i;
29        }
30        else
31        {
32            QuickSort(keys, i, hi);
33            hi = j;
34        }
35    }
36}

When the scan indices reach the pivot element, the algorithm compares the pivot to itself. Eliminating this comparison would require an extra conditional check on every iteration, which costs more than the occasional redundant comparison.

Writing a Correct Custom Comparer

A well-behaved comparer must handle self-comparison correctly by returning 0:

1class PersonAgeComparer : IComparer<Person>
2{
3    public int Compare(Person x, Person y)
4    {
5        // This naturally handles x == y (same reference)
6        // because x.Age.CompareTo(x.Age) returns 0
7        return x.Age.CompareTo(y.Age);
8    }
9}
10
11// Multi-key comparer
12class PersonComparer : IComparer<Person>
13{
14    public int Compare(Person x, Person y)
15    {
16        int result = string.Compare(x.LastName, y.LastName, StringComparison.Ordinal);
17        if (result != 0) return result;
18        result = string.Compare(x.FirstName, y.FirstName, StringComparison.Ordinal);
19        if (result != 0) return result;
20        return x.Age.CompareTo(y.Age);
21    }
22}
23
24var people = new List<Person>
25{
26    new("Alice", "Smith", 30),
27    new("Bob", "Jones", 25),
28    new("Charlie", "Smith", 35)
29};
30
31var sorted = people.OrderBy(p => p, new PersonComparer()).ToList();

When Self-Comparison Causes Problems

If your comparer violates the reflexivity rule (Compare(x, x) must return 0), LINQ may produce incorrect or unstable results:

1// BAD: Broken comparer that does not return 0 for self-comparison
2class BrokenComparer : IComparer<int>
3{
4    private int _callCount = 0;
5
6    public int Compare(int x, int y)
7    {
8        // Bug: using mutable state makes this non-deterministic
9        _callCount++;
10        if (_callCount % 3 == 0) return 1; // Random wrong result
11        return x.CompareTo(y);
12    }
13}
14
15// This may produce incorrectly sorted output
16var broken = numbers.OrderBy(n => n, new BrokenComparer()).ToList();

Using Comparison Delegate Instead

For simpler cases, use the Comparison<T> overload to avoid creating a full comparer class:

1var people = new List<Person>
2{
3    new("Alice", 30),
4    new("Bob", 25),
5    new("Charlie", 35)
6};
7
8// Lambda-based ordering
9var sorted = people.OrderBy(p => p.Age).ToList();
10
11// Or with List.Sort using Comparison<T>
12people.Sort((a, b) => a.Age.CompareTo(b.Age));
13
14// Multi-key with ThenBy — no custom comparer needed
15var multiSorted = people
16    .OrderBy(p => p.LastName)
17    .ThenBy(p => p.FirstName)
18    .ThenBy(p => p.Age)
19    .ToList();

Using key selectors with OrderBy/ThenBy is usually preferable to writing custom comparers.

Common Pitfalls

• Comparers that do not return 0 for equal elements: The sorting contract requires that Compare(x, x) == 0 (reflexivity), Compare(x, y) == -Compare(y, x) (antisymmetry), and transitivity. Violating these produces undefined sorting behavior — elements may appear in any order, or the sort may loop indefinitely.
• Using mutable state in comparers: A comparer that changes its behavior based on internal state (call count, random values) breaks the sorting contract. Comparers must be pure functions of their two arguments.
• Assuming a specific number of comparisons: The exact number and order of comparisons depend on the sorting algorithm and the input data. Do not write code that relies on a specific comparison sequence — it may change between .NET versions.
• Null reference exceptions in custom comparers: If your collection may contain null elements, your comparer must handle nulls explicitly. Comparer<T>.Default handles nulls by sorting them first, but custom comparers do not automatically.
• Expecting LINQ sort to be stable without ThenBy: LINQ's OrderBy is documented as a stable sort (equal elements preserve their original order), but this relies on the comparer correctly identifying equal elements. If Compare(x, y) returns non-zero for logically equal elements, stability is effectively lost.

Summary

• LINQ-to-Objects' sorting algorithm compares items to themselves as a natural consequence of its quicksort-based partitioning
• This is not a bug — it would be more expensive to check for and skip self-comparisons than to perform them
• Custom comparers must be reflexive (Compare(x, x) == 0), antisymmetric, and transitive
• Prefer key selectors (OrderBy(p => p.Age)) over custom IComparer<T> implementations when possible
• LINQ's OrderBy is a stable sort — equal elements maintain their original relative order
• Never use mutable state or side effects inside a comparer