Go rant

[Andrei Alexandrescu]

Daniel de Kok wrote:
> On 2009-12-18 20:39:08 +0100, Walter Bright <newshound1 at digitalmars.com> 
> said:
>> Ain't that cool? But look closer. The advantage of quicksort is that 
>> it is an *in-place* sort. The Haskell one creates new arrays for every 
>> state in the sort.
> 
> But it does have one nice property: due to laziness, the n-th elements 
> of the sorted array can be found without sorting the full array (except 
> of course, the largest two n's).

According to what I've read while looking into the subject, whether the 
concatenations are lazy or not depends on the language and a number of 
implementation vagaries.

Even assuming perfect, overhead-free laziness and ignoring the cost of 
all allocations and concatenations, in the worst case (reverse sorted 
array) just seeing the top 1 smallest element requires O(n*n) work. It's 
an uphill battle finding anything good about functional qsort. It's bad 
through and through.

(For solving the selection problem there are better methods - all use 
mutation and are very difficult to express in a functional language.)


Andrei