Array.Sort in with nontrivial comparison function

Question

Consider the following code from C# 5.0 in a Nutshell, p. 289:

int[] numbers = { 1, 2, 3, 4, 5 };
Array.Sort (numbers, (x, y) => x % 2 == y % 2 ? 0 : x % 2 == 1 ? -1 : 1); 

which gives result {3, 5, 1, 2, 4}.

I tried this on a paper and got {1, 3, 5, 2, 4}.

Why computer sorting gave 3 > 5 > 1 ?

Answer 1

Most likely the topic is about the fact that Sort does not guarantee the order of elements which are equal. Unlike stable sort algorithms that preserve original order of equal elements "unstable sort" may swap them. Normally when you do sorting by hand you do "stable sort" version.

Array.Sort:

This implementation performs an unstable sort; that is, if two elements are equal, their order might not be preserved. In contrast, a stable sort preserves the order of elements that are equal.

The sort function used in sample makes 1 == 3, 1 == 5 so unstable sort is allowed to order this numbers in any way as long as they are in correct order compared to other ones: 1,3,5 (stable - same order as in source) or any sequence 3,1,5 (unstable sort).

I.e. OrderBy implements "stable sort" and you can see results in following sample using the same compare function:

void Main()
{
    int[] numbers = { 1, 2, 3, 4, 5 };
    var result = numbers.OrderBy(x=> x, new MyComparer()));
      // 1, 3, 5, 2, 4
}

public class MyComparer : IComparer<int>  
{
    public int Compare( int x, int y)
    {
      return  x % 2 == y % 2 ? 0 : x % 2 == 1 ? -1 : 1;
    }
}

Answer 2

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.

Answer 3

That code is equivalent to:

static void Main(string[] args)
{
    int[] numbers = { 1, 2, 3, 4, 5 };
    Array.Sort(numbers, OnComparison); 
}

private static int OnComparison(int x, int y)
{
    if (x%2 == y%2) return 0;
    if (x%2 == 1) return 1;
    return -1;
}

I get:

{3, 5, 1, 2, 4} 

The sorting operation goes like this:

0) {1,2,3,4,5}
1) {1,2,3,4,5}
2) {1,2,3,4,5}
3) {1,2,3,4,5}
4) {1,2,3,4,5}
5) {5,2,3,4,1}
6) {5,2,3,4,1}
7) {5,2,3,4,1}
8) {5,3,2,4,1}
9) {5,3,2,4,1}
10) {5,3,2,4,1}
11) {5,3,2,4,1}
12) {3,5,2,4,1}
13) {3,5,2,4,1}
14) {3,5,1,4,2}
15) {3,5,1,4,2}
16) {3,5,1,4,2}
17) {3,5,1,4,2}
18) {3,5,1,2,4}
19) {3,5,1,2,4}
20) {3,5,1,2,4}
21) {3,5,1,2,4}
22) {3,5,1,2,4}
23) Final: {3,5,1,2,4}

So in conclusion, it seems the "why" is because the 0 problem as everybody says, but I am not completelly sure yet.

Answer 4

Here you are not sort equal remainders how you got in order

try this:

Array.Sort(numbers, (x, y) => x % 2 == y % 2 ? x < y ? 1 : -1 : x % 2 == 1 ? -1 : 1);