[Tim]
>> A larger lesson: even if Python gets a stable sort and
>> advertises stability (we don't have to guarantee it even if
>> it's there)
[/F]
> if we guarantee it, all python implementors must provide one.
Or a middle ground, akin to CPython's semi-reluctant guarantees of refcount
semantics for "timely" finalization. A great many CPython users appear
quite happy to rely on this despite that the language doesn't guarantee it.
> how hard is it to implement a reasonably good stable sort from
> scratch?
A straightforward mergesort using a temp vector of size N is dead easy, and
reasonably good (O(N log N) worst case). There aren't any other major N log
N sorts that are naturally stable, nor even any I know of (and I know of a
lot <wink>) that can be made stable without materializing list indices (or a
moral equivalent). Insertion sort is naturally stable, but is O(N**2)
expected case, so is DOA.
> I can think of lots of really stupid ways to do it on top of existing
> sort code, which might be a reason to provide two different sort
> methods: sort (fast) and stablesort (guaranteed, but maybe not
> as fast as sort). in CPython, both names can map to timsort.
I don't want to see two sort methods on the list object, for reasons
explained before. You've always been able to *get* a stable sort in Python
via materializing the list indices in a 2-tuple, as in Alex's "stable sort"
DSU recipe:
http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/52234
People overly <wink> concerned about portability can stick to that.
> (shouldn't you be writing a paper on this, btw?
I don't think there's anything truly new here, although the combination of
gimmicks may be unique. timsort.txt is close enough to a paper anyway, but
better in that it only tells you useful things; the McIlroy paper covers all
the rest <wink>.
> or start a sort blog ;-)
That must be some sort of web thing, hence beyond my limited abilities.
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