Array.Sort in with nontrivial comparison function

algorithm, c#, lambda, sorting

Solution

Although Array.Sort specifies

If the partition size is fewer than 16 elements, it uses an insertion sort algorithm.

it does not specifiy how it does this insertion sort or which flavor of insertion sort it uses. As already mentioned, it additionally specifies

This implementation performs an unstable sort

and as a result, the only thing `Array.Sort` promises about the order of the elements after returning is that they are sorted. This is true for `{3, 5, 1, 2, 4}`.

Consider that the algorithm used by `Array.Sort` would even be allowed to do something like this (Pseudocode):

if sequence = {1, 2, 3, 4, 5} then
    sequence := {3, 5, 1, 2, 4}
end if
Sort(sequence);

This, of course, would be implementation defined behavior, and it could change in another version of the .NET framework.

Modifying your code to be

Array.Sort(numbers, (x, y) =>
    {
        Console.WriteLine(x + ", " + y);
        return x % 2 == y % 2 ? 0 : x % 2 == 1 ? -1 : 1;
    });

will give you the comparisons that are done by `Array.Sort`:

1, 3
1, 5
3, 5
1, 3
3, 5
2, 3
3, 4
3, 3
5, 3
5, 3
5, 5
5, 3
2, 4
2, 1
4, 2
1, 4
4, 4
4, 2
1, 2
1, 2
1, 1
1, 2
1, 1

And this, very likely, is not how you would do an insertion sort on paper.

The point is: `Array.Sort` promises to sort your sequence, but it does not promise how to do this.

Problem

Original source