tim-peters

9 ms·

1.
by tim-peters 2y ago
I want to elaborate on timing cautions: a sort that specializes to 4-byte machine ints is doing something that can't be expressed directly in CPython. Its lists are heterogeneous, types aren't known until runtime, and there is no
2.
by tim-peters 2y ago
Ya, I'm just too old for bottomless pits anymore ;-) Patience sorting is still worth study, for its elegance, simple code, and real-world practicality in the context of solving the longest increasing subsequence problem. As a full-blow
3.
by tim-peters 2y ago
You're much more up to date on the details of recent developments than I am. It's faded into a background interest (although a persistent one) for me. One thing that wasn't clear to me about JesseSort: in what way(z) are Rain
4.
by tim-peters 2y ago
I want to thank you for your analysis! I'm the "timsort" guy, and I'm asked to look at all sorts of things. The devil is in the details, and I've given up bothering to look unless a paper spells out sufficient detai
5.
by tim-peters 2y ago
Perhaps ;-) I'm the "Tim" in "timsort". The name was an inside joke. I'm not a self-promoter, and never have been. As the so-called "Zen of Python" author, I thought it would be funny to pick a name I
6.
by tim-peters 5y ago
Sorry, nope. There aren't n permutations you're searching through, but the factorial of n to search through. That's the heart of the information-theoretic proof that no comparison-based sorting algorithm can do better, on
7.
by tim-peters 5y ago
Haha. AdamMerge works for me - I get enough abuse for naming a sort after myself ;-) If you pursue this, you can probably throw out piles of the CPython code. That's trying to keep the result "in place", so has major code ne
8.
by tim-peters 5y ago
See CPython's https://github.com/python/cpython/blob/main/Objects/listsort... for details about the sort. In fact, its "galloping" was inspired by a paper of which Demaine was a co-au
9.
by tim-peters 5y ago
You already got a win - quit while you're ahead ;-) Note that plain binary search here is probably not a good idea. See "listsort.txt", in the same directory as "listobject.c", for excruciating details.
10.
by tim-peters 5y ago
Right, `merge_at()`. But that in turn calls small mountains of other C code. It is, alas, a complicated approach. Folding it in would be substantially more work than you've already done. The point: for inputs like your: a = list(range
11.
by tim-peters 5y ago
To get more gonzo, in CPython's list.sort(), the C code that actually merges two lists (which happen, in context, to be two contiguous array slices) is in listobject.c's `merge_at(()` function. That brings in the world of "ga