使用 IEnumerable 实现的快速排序的复杂度是多少？

Question

我想知道这篇文章中实现的快速排序的复杂性。Stuart Marks 说它是 O(N^2 log N)。但真的是这样吗？我不明白这些词：在我看来 - 再一次，我不是 C# 或 .NET 专家 - 这将导致某些看起来无害的调用，例如通过 ints.First() 进行枢轴选择，比它们看起来更昂贵. 在第一层，当然是 O(1)。但是考虑在树深处的右侧边缘的分区。要计算此分区的第一个元素，必须遍历整个源，这是一个 O(N) 操作。但是由于上面的分区是惰性的，它们必须重新计算，需要 O(lg N) 次比较。因此，选择主元将是一个 O(N lg N) 操作，这与整个排序一样昂贵。为什么ints.First()是 O(N) 操作？我认为它总是 O(1)。为什么IEnumerables必须重新计算上面树中的分区？这对我来说也没有任何意义。不IEnumerable.Where返回新的 IEnumerable 吗？在我看来，这个算法的时间复杂度仍然是 O(N log N)，但空间复杂度也是 O(N log N)，而不仅仅是我们就地排序的 O(N)。总而言之，Stuart Marks 是对还是我对？