[cperciva]

As the saying goes, "memory is the new disk". Data structures like B-trees which were designed to improve the performance of data accesses from disk are now useful for improving the performance of algorithms in memory.

[delhanty]

Does anybody have any data on whether external sorting [1] is the way to go these days for CPU based sorts?

That is, use quicksort for chunks up to the size of the L1/L2/L3 cache (depending on benchmarking) and then mergesort the chunks.

[1] https://en.wikipedia.org/wiki/External_sorting

[adrianN]

You can have a look at the best sorting algorithms (for various definitions of "best") here http://sortbenchmark.org/

[cperciva]

That's for big sorts. The question here is about sorting with a single CPU.

[adrianN]

Look at the Joule category.

[cperciva]

I don't have any data readily available, but it's generally understood that you want a cache-aware sort, yes. Usually I see people opt for samplesort rather than sorting chunks and merging, though.

[delhanty]

Thanks for your opinion.

I did not know about samplesort - found it on Wikipedia.