sorting many arrays from one...

[Tim Peters]

[Alex Martelli]
> ...
> It so happens that Python list's sort method is the best-performing sort
> I've ever seen deployed in production code for many special cases of
> enormous practical importance

See how calm my reply here is?  Let this be a lasting retort to all who say
I can't take criticism <wink>.

> (lists that are close to being ordered

Unfortunately, it's only some lists that are close to being ordered,
although I believe it catches the most frequent real-life cases of that.
"Close to being ordered" in general == few inversions, and that general
criterion includes cases like

    [2, 1] + range(3, 1000000)

That *could* be sorted with one swap and about a million compares to verify
that the remainder is already sorted.  list.sort() doesn't realize that,
though.  I hope to go back someday and generalize the special-casing to
handle all few-inversion cases quickly; as-is, it only catches cases where
few inversions follow a long prefix that's already sorted or reverse-sorted.
Those seem to be most frequent in practice, although Aaron Watters made a
strong argument for why general few-inversions cases are likely to arise in
some computational geometry algorithms.  But if I remembered his argument
now, I would have presented it as my own instead of bothering to give him
credit <wink>.

there's-always-50-more-lines-to-write-and-70-to-throw-away-ly y'rs  - tim