Re: Soundness of table.sort

[Roberto Ierusalimschy <roberto@...>]

> > When Albert Nijenhuis and Herbert Wilf wrote their seminal work
> > "Combinatorial Algorithms" back in 1975, they chose Heapsort
> > as the preferred sorting method because it is in-place, has O(n*log(n))
> > worst-case time, and among all algorithms with these two properties
> > known at the time was shortest to code (23 lines of Fortran) . I think
> > it still holds that particular record.
> 
> Nevertheless, its memory access pattern is not the best for current machines.

Quite the opposite... While quicksort has an almost perfect behavior
regarding memory locallity (caches and pages), Heapsort touches the
entire array space at each single step. That often makes it much slower
than quicksort for large arrays, despite the same complexity.

-- Roberto