Selection algorithm using merge sort and IEnumerable For educational purposes, I wrote a selection algorithm based on a Merge sort. I would like to improve performance.

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)
    {
        yield return list[left];
        yield break;
    }

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

    //merge
    using (var firstEnumerator = firstEnumerable.GetEnumerator())
    using (var secondEnumerator = secondEnumerable.GetEnumerator())
    {
        bool first = firstEnumerator.MoveNext();
        bool second = secondEnumerator.MoveNext();

        while (first &amp;&amp; second)
        {
            if (comparer.Compare(firstEnumerator.Current, secondEnumerator.Current) &lt; 0)
            {
                yield return firstEnumerator.Current;
                first = firstEnumerator.MoveNext();
            }
            else
            {
                yield return secondEnumerator.Current;
                second = secondEnumerator.MoveNext();
            }
        }

        while (first)
        {
            yield return firstEnumerator.Current;
            first = firstEnumerator.MoveNext();
        }

        while (second)
        {
            yield return secondEnumerator.Current;
            second = secondEnumerator.MoveNext();
        }
    }
}


What it does : it recursively divide the list into smaller sequences (until the sequence has only one element). Then, it repeatedly merge sequences to produce new sorted ones until there is only 1 sequence remaining. 

The main idea is to use IEnumerable&lt;T&gt; so there is no need to allocate arrays to merge results AND I can sort the list lazily and stop when I want. Example : 

var list = ... // 1.000.000 elements 
MergeSort(list, 0, list.length - 1, comparer).Take(50);


The actual performance to sort 1M integers and return the first 50 ones is 600 ms why I found to be slower than expected.  Returning only the first element give a similar performance.

My main concern is the recursive calls between Enumerators/IEnumerables. I have tried to wrote the same logic using a stack (to fully avoid recursion) but I don't know how to implement it.

I have also tried to isolate the merge code part (the code inside the two usings statements) into a separate method but it run considerably slower (about 1 sec). I don't know why.

I could easily parallelise the algorithm or use another selection algorithm (like quick select) but this is outside the scope of this question.
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.