Unclear Lambda expression to Array.Sort static function

Question

I'm looking at an example on how to sort an int[] array with the Array.Sort function, where a lambda expression is passed as a Comparison<T> (T x, T y) delegate to sort all the integers in the array making it able to place odd numbers first. Here's the code :

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

How is Array.Sort() actually calling x & y ? would anyone provide me a step by step explanation for that lambda ?

Answer 1

See Int32.CompareTo for the sorting method that this lambda expression is replacing. Normally, we'd have:

• x < y: return -1
• x == y: return 0
• x > y: return 1

Instead, we have:

• x odd, y even: return -1
• x odd, y odd OR x even, y even: return 0
• x even, y odd: return 1

Since the elements in the sets {1, 3, 5} are equal and {2, 4} are equal, you're at the mercy of the sorting algorithm used for the exact order of the final set. The sorted list will have the form {odds, evens}, but the orders of those sublists will depend on the algorithm. Per MSDN, Array.Sort uses Insertion sort if the array has fewer than 16 elements.

When I do this, the order I get back is {1, 3, 5, 2, 4}, which is what I would expect, not {3, 5, 1, 2, 4}

UPDATE: It was pointed out in the comments that x % 2 == -1 for negative odd integers, which means that the above needs some reworking for the general int. (I apologize, but my math background means I think of mod as an unsigned value.)

• x odd, y even OR (x odd, y odd, x > 0 > y): return -1
• (x odd, y odd, same sign) OR x even, y even: return 0
• x even, y odd OR (x odd, y odd, x < 0 < y) : return 1

This will mean that we end up with a list of the form {positive odds, negative odds, evens}.

Answer 2

The comparison function type (T, T) => int is more general-purpose, but it can be a nuisance in some common cases. The lambda expression in your question is sorting numbers based on their values modulo 2, but the way it is written doesn't make that clear.

If you want to compare items based on some key, you can do that using the following helper method.

public static class Functional
{
    public static Func<T, T, int> KeyComparison<T, K>(Func<T, K> key)
        where K : IComparable<K>
    {
        return (x, y) => Comparer<K>.Default.Compare(key(x), key(y));
    }
}

Usage:

Array.Sort(numbers, Functional.KeyComparison(x => x % 2));

This sorts your numbers in the same way as before, based on their value modulo 2, but in a way that is more legible.