基于IEnumerable实现的快速排序时间复杂度存疑：谁的观点正确？

我对一篇讨论快速排序实现的内容里，基于IEnumerable实现版本的时间复杂度存疑。Stuart Marks认为它的时间复杂度是O(N²logN)，但我完全搞不懂他下面这段表述：

在我看来——再次声明，我并非C#或.NET专家——这会导致一些看似简单的调用（例如通过ints.First()选择基准元素）的开销远超预期。在第一层，它自然是O(1)操作，但考虑树中深处右侧的某个分区，要获取该分区的第一个元素，必须遍历整个源数据，这是O(N)操作。由于上层分区是延迟加载的，它们必须被重新计算，需要O(lgN)次比较。因此选择基准元素的操作复杂度为O(N lgN)，相当于一次完整排序的开销。

我有两个核心疑问：

• 为什么ints.First()会变成O(N)操作？我一直以为它始终是O(1)的啊。
• 为什么IEnumerable树里的上层分区需要重新计算？IEnumerable.Where不是会返回一个新的IEnumerable实例吗？

在我的理解里，这个算法的时间复杂度应该还是O(N logN)，只是空间复杂度是O(N logN)，和原地排序的O(N)不一样。

想请教一下，到底Stuart Marks和我的观点谁是正确的？

内容的提问来源于stack exchange，提问作者Coder-Man