ch-ch-changes

[Andrei Alexandrescu]

Christopher Wright wrote:
> Andrei Alexandrescu wrote:
>> A stride is a great way to get a good pivot into a large array when 
>> sorting. You sort the stride and then get its median.
> 
> I'm not so sure about that. If the array is in fact large, you're 
> dealing with an external memory situation, and sorting the stride means 
> you have to touch every single block of the array. If your stride is 
> even larger than a block, you could change this, but caches are all 
> designed around sequential access, so they'll defeat you even if you are 
> that clever.
> 
> So, using the stride of an array to find a pivot will double the amount 
> of time it takes to sort the array in the worst case.

I thought about it some more and figured an exponential stride (e.g. 1, 
16, 32, 64 ...) might do the trick. It's easy to compute, spans the 
entire array, and the number of cache blocks fetched grows with log N.


Andrei