4 ms·
JVM and Python use timsort, which is O(N) on mostly sorted data of all kinds.
by kazagistar 8y ago
JVM and Python use timsort, which is O(N) on mostly sorted data of all kinds.
- sova 8y agotimsort is full of win, and such a clever approach.
- lorenzhs 8y agoI'm sorry, but Timsort is a bit of a hack. It's a "this seems to work well" algorithm, and it shows. It took 13 years until its claimed running time was finally proven in 2015. The four (originally three) rules for merging sequences from the stack are rather arbitrary. Multiple issues were found well after it was already widely deployed. Recently, it was also shown that Timsort doesn't optimally use the information it has about runs. As an alternative, powersort was proposed, which seems to outperform Timsort both on randomly ordered inputs as well as inputs with long runs: https://arxiv.org/pdf/1805.04154.pdf https://arxiv.org/pdf/1805.04154.pdf