> First, the traditional implementation of QuickSort has an implicit (or virtual?) intermediate data structure, the function call tree. That's a good point, bu

> First, the traditional implementation of QuickSort has an implicit (or virtual?) intermediate data structure, the function call tree. That's a good point, but function calls have a constant cost in terms of stack frame allocation and deallocation. > Second, I have limited understanding of lazy evaluation, but in a lazy language I believe ‘flatten’ would begin consuming the tree as it is still being built by ‘build’. Yes, that is correct. The entire tree is not allocated at once, only the nodes that are actually needed, as well as dynamic data representing suspended computations of the rest of the data structure. But (again, ignoring compiler optimizations that would make them go away) these are allocations on the garbage-collected heap and thus incur GC costs and complexity. Overall I agree that there would be value in illustrating algorithms by also showing the version that constructs the computation tree. But I don't think it should be the one presentation of the algorithm, only a device to further understanding of the "real" implementation.