random cover of a range

[Andrei Alexandrescu]

bearophile wrote:
> Andrei Alexandrescu:
>> Well we were discussing how to tackle the algorithm that does not touch 
>> the original array/range.
> 
> What I have said so far applies still: at the end instead of copying the remaining 10% of the items, create an array of the indexes of those 10%, and then shuffle that.

I understood that. My problem is that a quadratic algorithm is applied 
to 0.9 of the input. That makes overall behavior quadratic even if you 
complete the last 10% in no time.

Andrei