Clarification on Lazy Evaluation and its efficiency

Question

I came across following sentence on Real World Haskell:

Lazy evaluation has some spooky effects. Let's say we want to find the k least-valued elements of an unsorted list. In a traditional language, the obvious approach would be to sort the list and take the first k elements, but this is expensive. For efficiency, we would instead write a special function that takes these values in one pass, and it would have to perform some moderately complex book-keeping. In Haskell, the sort-then-take approach actually performs well: laziness ensures that the list will only be sorted enough to find the k minimal elements.

And they give an code implemntation for that:

minima k xs = take k (sort xs)

But is that so ? I think even in Haskell it should do a full sort of the list to take out the k elements. ( Imagine having the smallest number at the end of the list ). Am I missing something here ?

Answer 1

(Just putting my comment to answer here) Traversing the whole list is not equivalent to sorting it. Assume doing quicksort where you partition the list around the pivot and then recursively sort left and right half of the list. If you are asking just for elements on the left half then there is no need to sort the right half. This argument can be applied recursively. Thus if you are taking k elements from n length list after sorting, the complexity is O(n + klog k) and not O(n log n). As pointed by @MoFu, Heinrich has a good blog post here.