--- Tim Peters <tim.one@comcast.net> wrote: > In an effort to save time on email (ya, right ...), I wrote up a pretty > detailed overview of the "timsort" algorithm. It's attached. > > all-will-be-revealed-ly y'rs - tim > > [Interesting stuff deleted.] > I'm curious if there is any literature that you've come across, or if you've done any experiments with merging more than two parts at a time. So instead of merging like such: A B C D E F G H I J K L AB CD EF GH IJ KL ABCD EFGH IJKL ABCDEFGH IJKL ABCDEFGHIJKL You were to merge A B C D E F G H I J K L ABC DEF GHI JKL ABCDEF GHIJKL ABCDEFGHIJKL (I realize that your merges are based on the lengths of the subsequences, but you get the point.) My thinking is that many machines (probably yours for instance) have a cache that is 4-way associative, so merging only 2 blocks at a time might not be using the cache as well as it could. Also, changing from merging 2 blocks to 3 or 4 blocks at a time would change the number of passes you have to make (the log part of N*log(N)). It's quite possible that this isn't worth the trade off in complexity and space (or your time :-). Keeping track of comparisons that you've already made could get ugly, and your temp space requirement would go from N/2 to possibly 3N/4... But since you're diving so deeply into this problem, I figured I'd throw it out there. OTOH, this could be close to the speedup that heavily optimized FFT algs get when they go from radix-2 to radix-4. Just thinking out loud... __________________________________________________ Do You Yahoo!? Yahoo! Health - Feel better, live better http://health.yahoo.com
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