[Guido] >> Ah, but then Dan will just add Karatsuba multiplication to Parrot, >> too. And AFAIK, Timsort isn't patented. :-) [Delaney, Timothy C (Timothy)] > True. But do you really expect that anyone except Tim could get it > *right*??? Yup! I documented the approach in soul-numbing detail. Last I saw, Perl had an adaptive mergesort too, and in principle that's the same thing. The Python implementation is a lot more long-winded, because it's trying harder to use less memory and be friendlier to the cache, uses only less-than instead of Perl's 3-outcome comparison primitive, and tries harder to minimize wasted comparisons if the data turns out to be random -- but that's all shallow complication. The core idea can be explained in less than 50 pages of dense text <wink>. OK, in less than 50 words: when one input to a merge "wins" several times in a row, you can potentially save a ton of comparisons by skipping ahead. All the rest is engineering.
RetroSearch is an open source project built by @garambo | Open a GitHub Issue
Search and Browse the WWW like it's 1997 | Search results from DuckDuckGo
HTML:
3.2
| Encoding:
UTF-8
| Version:
0.7.4