Worst-case performance of quickSort / getPivot

[Vladimir Panteleev]

On Sunday, 17 November 2013 at 05:30:24 UTC, Jean Christophe 
wrote:
>> You mean, sort!`a.foo < b.foo` ?
>
> Yes.
>
> An indirect sorting, assuming a and b to be ojects of class 
> SomePotentialyLargeClass.
>
> Because the array to sort contains pointers only, all the data 
> movement is essentially the same as if we were sorting integer.

If the range elements are reference types, that's what will 
happen (unless they overload opAssign oslt). Otherwise, there's 
makeIndex (already mentioned by Andrei), or you could also do it 
by hand:

1. r.length.iota.array.sort!((a, b) => r[a]<r[b]);
2. r.length.iota.map!(a => &r[a]).array.sort!((a, b) => *a<*b);

r.map!`&a` doesn't work though, because we don't get a reference 
to the range element in the predicate.