寻求IEnumerable<T>最优且优雅的有序插入算法实现方案

这是一个非常棒的问题——既要保持单次枚举的高效性，又要避免冗余的状态变量，确实需要巧思。我来分享一个既优雅又高效的实现，完全不需要额外的状态变量，同时处理所有边界情况：

public static IEnumerable<T> InsertInOrder<T>(this IEnumerable<T> source, T insertion) where T : IComparable<T>
{
    using var enumerator = source.GetEnumerator();
    
    // 遍历所有比插入元素小的元素
    while (enumerator.MoveNext())
    {
        if (enumerator.Current.CompareTo(insertion) < 0)
        {
            yield return enumerator.Current;
        }
        else
        {
            // 找到插入位置：先返回待插入元素，再返回当前元素
            yield return insertion;
            yield return enumerator.Current;
            
            // 一次性遍历剩余所有元素，无额外条件检查
            while (enumerator.MoveNext())
            {
                yield return enumerator.Current;
            }
            
            // 完成所有遍历，直接退出
            yield break;
        }
    }
    
    // 若所有元素都小于插入元素，直接追加到末尾
    yield return insertion;
}

实现优势解析 #

1. 单次枚举，极致高效：整个过程只枚举source一次，避免了像你第一个实现中TakeWhile+SkipWhile导致的重复遍历问题，时间复杂度严格为O(n)，内存占用仅为枚举器本身的开销。
2. 无冗余状态变量：完全不需要inserted、movedNext这类额外变量，通过嵌套的while循环和yield break直接控制流程，逻辑清晰直观。
3. 边界情况全覆盖：
   • 插入到集合开头：第一个元素就大于等于插入元素时，直接先返回插入元素再遍历所有元素
   • 插入到集合中间：找到第一个不小于插入元素的位置，插入后继续遍历剩余元素
   • 插入到集合末尾：遍历完所有元素后，最后返回插入元素
   • 空集合：直接返回仅包含插入元素的枚举
4. 惰性执行：和LINQ原生方法保持一致，只有在迭代结果时才会执行枚举逻辑，适合处理大数据量或惰性生成的集合。

对比你之前的实现 #

• 你的第一个实现虽然代码简洁，但两次枚举source的问题在source是惰性集合（比如动态生成的LINQ查询）时会导致严重的性能损耗，甚至可能产生不一致的结果。
• 第二个实现中的inserted变量会导致每次循环都要做冗余的条件判断，虽然性能差异不大，但代码不够简洁。
• 第三个实现的movedNext变量确实减少了条件判断，但赋值和判断合并的写法可读性较差，且依然依赖额外变量。

这个实现完美解决了你提到的“意外移动过远”的问题——一旦找到插入点，我们直接插入元素，然后一次性遍历剩余所有元素，没有回溯或多余的移动操作。

内容的提问来源于stack exchange，提问作者user7127000