Here's another challenge, "Binary search an array of int without boxing", I'll even give you the wrong answer "Use the generic Array.BinarySearch<T>(T[], T) method".

int[] ints = new int[] { 1 };
int index = Array.BinarySearch<int>(ints, 1);

Try running the second line 100,000 times in the CLR Profiler and you'll see a good 2.3mb or so of heap allocations. The cause as shown by the CLR Profiler lies in GenericArraySortHelper<T>. BinarySearch(T[], Int32, Int32, T). The corresponding C# probably looks something like this:

if (array[mid] == null)
    cmp = (value == null) ? 0 : -1;
else
    cmp = array[mid].CompareTo(value);

In IL, that comparison against null looks like this:

ldarg 'value'
box !T
brfalse 'somewhere'

The box instruction is something you really don't want to see in a code path that accepts ValueTypes. One way to avoid it would have been a separate ArraySortHelper for dealing with value types - but for now no such class exists.

The BCL authors of this specific area seem to have been unaware of the boxing, at least that's what these comments from the SSCLI/2.0 seem to indicate:

// This function is called when the user doesn't specify any comparer.
// Since T is constrained here, we can call IComparable<T>.CompareTo here.
// We can avoid boxing for value type and casting for reference types.

On further examination Array.Sort<T>, Comparer<T>.Default and EqualityComparer<T>.Default seem to be equally broken for value types. This is a pretty serious issue, even more so since Array.Sort/BinarySearch is used internally by List<T>. IEquatable<T> and thus a default EqualityComparer<T> is used by List<T>.Contains and much of Dictionary<T,U>. I'm surprised EqualityComparer<T> now seems to be boxing since I vaguely remember using IEquatable<T> to solve boxing in a Dictionary once before.

I have filed a bug here on connect.microsoft.com.

There are workarounds, but they require writing your own code, the easiest is to pass your own IComparer<T>.

Update (11 July): Maybe we can breathe a little easier, it looks like the problem may only occur on the x64 CLR. I guess the x86 JIT is smart enough to skip over the box/brfalse instructions!