[Haskell-cafe] Time and space complexity of "take k . sort"

[Paul Johnson]

This question on StackOverflow asked about how to find the largest 100 
items in a very long list:

http://stackoverflow.com/questions/1602998/fastest-way-to-obtain-the-largest-x-numbers-from-a-very-large-unsorted-list/1603198#1603198

I replied that you could do it with something like this (but here taking 
the k smallest to strip out some irrelevant complications):

 >  takeLargest k = take k . sort

Because "sort" is lazily evaluated this only does enough sorting to find 
the first k elements.  I guess the complexity is something like 
O(n*k*log(k)).

But of equal practical interest is the space complexity.  The optimum 
algorithm is to take the first k items, sort them, and then iterate 
through the remaining items by adding each item to the sorted list and 
then throwing out the highest one.  That has space complexity O(k).  
What does the function above do?

Paul.