3 ms·
I'd read somewhere [1] that the built-in Python sort function has a lot of good / clever optimizations too, though maybe not of the same kinds that you describe
by vram22 11y ago
I'd read somewhere [1] that the built-in Python sort function has a lot of good / clever optimizations too, though maybe not of the same kinds that you describe, i.e. may not be at machine language level. Tim Peters did a lot of that, per what I read, though others may have too.
[1] Think I read it in the Python Cookbook, 2nd Edition, which is a very good book, BTW.
- hayd 11y agoTime Peters wrote Timsort for python https://en.wikipedia.org/wiki/Timsort https://en.wikipedia.org/wiki/Timsort I think quite a few languages adopted it as their default sort.
- vram22 11y agoAh, I remembered his name, but had forgotten that it was called Timsort, thanks. Interesting that others also used it.
- andrewf 11y agoJava's standard lib uses Timsort for sorting Object[], and quicksort for arrays of primatives. http://stackoverflow.com/questions/4018332/is-java-7-using-tim-sort-for-the-method-arrays-sort http://stackoverflow.com/questions/4018332/is-java-7-using-t...
- nostrademons 11y agoDifferent kinds of optimizations. Timsort tries to collect runs and falls back on insertion sort for them; it exploits the fact that much real-world data is already partially sorted to reduce the number of comparisons made. This optimization exploits the fact that MapReduce keys are always strings in contiguous areas of memory, and are often fairly large, to compare them really quickly.