On Tue, Jun 18, 2013 at 6:11 PM, Jim Nasby <jim@nasby.net> wrote:
> IIRC there's some kind of compression or something used with on-disk sorts.
I think you're mistaken.
> If that's correct then I think what's happening is that the "on-disk" sort that fits into cache
> is actually using less memory than quicksort. Or perhaps it was just a matter of memory
> locality within each tape. It's been too long since I looked at it. :(
External sorts do of course use less memory, but quicksort is
particularly good at taking advantage of memory locality.
I think it's possible that what you recall is the days when we used
the OS qsort(), and we were at the mercy of the implementation that
the OS provided. When we effectively began to vendor our own sort
routine in 2006, we chose a high-quality one with various protections
against quadratic behaviors. Implementations that lacked these
protections were prevalent at a surprisingly late stage.
--
Peter Geoghegan
