Why is python's sorted called stable despite not preserving the original order?

Question

Summary

Sorting in Python is guaranteed to be stable since Python 2.2, as documented here and here.

Wikipedia explains what the property of being stable means for the behavior of the algorithm:

A sorting algorithm is stable if whenever there are two records R and S with the same key, and R appears before S in the original list, then R will always appear before S in the sorted list.

However, when sorting objects, such as tuples, sorting appears to be unstable.

For example,

>>> a = [(1, 3), (3, 2), (2, 4), (1, 2)]
>>> sorted(a)
[(1, 2), (1, 3), (2, 4), (3, 2)]

However, to be considered stable, I thought the new sequence should've been

[(1, 3), (1, 2), (2, 4), (3, 2)]

because, in the original sequence, the tuple (1, 3) appears before tuple (1, 2). The sorted function is relying on the 2-ary "keys" when the 1-ary "keys" are equal. (To clarify, the 1-ary key of some tuple t would be t[0] and the 2-ary t[1].)

To produce the expected result, we have to do the following:

>>> sorted(a, key=lambda t: t[0])
[(1, 3), (1, 2), (2, 4), (3, 2)]

I'm guessing there's a false assumption on my part, either about sorted or maybe on how tuple and/or list types are treated during comparison.

Questions

Why is the sorted function said to be "stable" even though it alters the original sequence in this manner?
Wouldn't setting the default behavior to that of the lambda version be more consistent with what "stable" means? Why is it not set this way?
Is this behavior simply a side-effect of how tuples and/or lists are inherently compared (i.e. the false assumption)?

Thanks.

Please note that this is not about whether the default behavior is or isn't useful, common, or something else. It's about whether the default behavior is consistent with the definition of what it means to be stable (which, IMHO, does not appear to be the case) and the guarantee of stability mentioned in the docs.

Again with the downvoters that don't even bother to provide an explanation. In what way does this question "not show any research effort, is unclear, or not useful"?... Those votes came before any reasonable amount of time needed to actually read the question had gone by... smh — code_dredd
I guess the downvoter consider it a lack of research that you only assume how tuples should be sorted. — GhostCat
@GhostCat While I can see that part of your feedback, I think it's unreasonable for anyone to assume that missing one detail negates the rest of the research that did go into it. In any case, I digress. — code_dredd
I didn't downvote, so I can only speculate. And honestly: I rarely see that questioners agree to downvotes. So that piece of information isn't exactly newsworthy. And just for the record: you focused your research on the stable part. You then assumed that your idea how tuples should be sorted is correct. Maybe some folks simply understand how well designed and "perfect" the python sort implementation is. So instead of asking "woha, why is python sort not stable" ... a title like "where is the flaw in my logic" would have resulted in less downvotes. But whatever. Nice question. — GhostCat
["the docs" is] a lot to read moreover, the bit about how sequences of the same type compare is not linked or repeated near the claim to stability. — greybeard

TerryA TerryA · Accepted Answer · 2017-09-01T10:44:24

Think about it - (1, 2) comes before (1, 3), does it not? Sorting a list by default does not automatically mean "just sort it based off the first element". Otherwise you could say that apple comes before aardvark in the alphabet. In other words, this has nothing to do with stability.

The docs also have a nice explanation about how data structures such as lists and tuples are sorted lexicographically:

In particular, tuples and lists are compared lexicographically by comparing corresponding elements. This means that to compare equal, every element must compare equal and the two sequences must be of the same type and have the same length.

Why is python's sorted called stable despite not preserving the original order?

Summary

Questions

3 Answers