3 ms·
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 us
by cperciva 9y ago
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 9y agoDoes 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 https://en.wikipedia.org/wiki/External_sorting
- cperciva 9y agoI 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 9y agoThanks for your opinion. I did not know about samplesort - found it on Wikipedia.
- adrianN 9y agoYou can have a look at the best sorting algorithms (for various definitions of "best") here http://sortbenchmark.org/ http://sortbenchmark.org/