On Thu, Apr 14, 2011 at 10:05 PM, Scott Carey <scott@richrelevance.com> wrote:
> Huge Pages helps caches.
> Dual-Pivot quicksort is more cache friendly and is _always_ equal to or
> faster than traditional quicksort (its a provably improved algorithm).
If you want a cache-friendly sorting algorithm, you need mergesort.
I don't know any algorithm as friendly to caches as mergesort.
Quicksort could be better only when the sorting buffer is guaranteed
to fit on the CPU's cache, and that's usually just a few 4kb pages.