[Steven D'Aprano <st...@pearwood.info>]
> ...
> All I intended was to say that sort would "work" in the sense you state:
> it will give *some* permutation of the data, where (I think, correct me
> if I'm wrong) each element compares less than the following element.
>
> Wait, no, that's not right either... each element doesn't compare less
> than the previous element?
There's really nothing useful that can be said without knowing precise
implementation details, and essentially nothing at all that can be
said about sorting-in-general, when a total order doesn't exist. Even
for a 2-element list! If the result of Python's sort is
[x, y]
then I happen to know (because I know everything about its
implementation) that one of two things is true:
- The original list was also [x, y], and y < x was False. But we
can't deduce anything about what x < y, x <= y, x == y, x != y. x > y,
x >= y, y <= x, y > x, y >= x, y == x, or y != x would do.
- The original list was [y, x], and x < y was True (but again we can't
deduce anything about what any other comparisons involving x and y
would do).
For longer lists it can get much more complicated; comparing adjacent
elements is just the first step in an algorithm with several stages,
which dynamically adjust to patterns of comparison outcomes that are
discovered as the algorithm goes along.
If we don't know the precise implementation, there's really nothing
crisp I can think of that necessarily follows from that the result is
[x, y].
And I think this must be so for any "reasonably efficient" sorting
algorithm. If there are N elements in the list, there are N*(N-1)
_possible_ pairwise __lt__ invocations that could be made, but an
efficient sort will never invoke more than O(N*log(N)) of them. The
ratio of comparisons made to the number that _could_ be made tends to
0 as N increases - and in that sense the sort explores "almost none"
of the possible comparison outcomes.
For that reason, it would be much more expensive to check that a
consistent total order exists than to do the sort. For the same
reason, you can't deduce much from the result without knowing
precisely which of the "nearly all of 'em" possible comparisons were
skipped.
_______________________________________________
Python-ideas mailing list -- python-ideas@python.org
To unsubscribe send an email to python-ideas-le...@python.org
https://mail.python.org/mailman3/lists/python-ideas.python.org/
Message archived at
https://mail.python.org/archives/list/python-ideas@python.org/message/X7WPNDUMQKU6RM3DI4HHXD6EE4N6AGWS/
Code of Conduct: http://python.org/psf/codeofconduct/
