Selection algorithm using merge sort and IEnumerable
I was able to get a performance increase (500 ms in average instead of 600 ms) by splitting the code in two methods : one that return a sequence with a single element, one that merge IEnumerables. I think this is faster because the implementation of the yield return statements is simpler for the compiler (AFAIK it is done using a state machine) .

public IEnumerable&lt;T&gt; MergeSort&lt;T&gt;(List&lt;T&gt; list, int left, int right, Comparer&lt;T&gt; comparer)
{
    if (left == right)
    {
        return SingleValue(list[left]);
    }

    int mid = (left + right) / 2;
    var firstEnumerable = MergeSort(list, left, mid, comparer);
    var secondEnumerable = MergeSort(list, mid + 1, right, comparer);
    return Merge(firstEnumerable, secondEnumerable, comparer);
}

public static IEnumerable&lt;T&gt; SingleValue&lt;T&gt;(T value)
{
    yield return value;
} 

public static IEnumerable&lt;T&gt; Merge&lt;T&gt;(IEnumerable&lt;T&gt; firstEnumerable, IEnumerable&lt;T&gt; secondEnumerable, Comparer&lt;T&gt; comparer)
{
    using (var firstEnumerator = firstEnumerable.GetEnumerator())
    using (var secondEnumerator = secondEnumerable.GetEnumerator())
    { 
         //same as before
    }
}


Performance can be improved further by checking the range of elements to sort inside MergeSort method. Above a certain threshold, another sort can be used (eg : InsertionSort or SelectionSort)

public IEnumerable&lt;T&gt; MergeSort&lt;T&gt;(List&lt;T&gt; list, int left, int right, Comparer&lt;T&gt; comparer)
{
    if (right - left &lt;= threshold)
    {
        return SelectionSort(list, left, right, comparer);
    }

    //...
}


I think SelectionSort is a good candidate because there is a way to implement it lazily : it can return the smallest number very early without having to sort the whole list  (eg: using a yield return). The partial merge sort now take about 15 ms to get the first 50th smallest numbers out of 1M integers.