Hacker Newsnew | past | comments | ask | show | jobs | submitlogin

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.


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


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


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


Look at the Joule category.


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.


Thanks for your opinion.

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




Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: