尽管没有保留原始顺序，为什么 python 的排序被称为稳定？

Question

概括

从 Python 2.2 开始，Python 中的排序保证是稳定的，如此处和此处所述。

维基百科解释了稳定的属性对算法的行为意味着什么：

一个排序算法是稳定的，如果当有两条记录 R 和 S 具有相同的键，并且 R 在原始列表中出现在 S 之前，那么 R 将始终出现在排序列表中的 S 之前。

但是，在对元组等对象进行排序时，排序似乎不稳定。

例如，

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

然而，为了稳定，我认为新的序列应该是

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

因为，在原始序列中，元组(1, 3)出现在 tuple 之前(1, 2)。sorted当一元“键”相等时，该函数依赖于二元“键”。（澄清一下，某些元组的 1-ary 键t将是t[0]2-ary t[1]。）

为了产生预期的结果，我们必须执行以下操作：

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

我猜我有一个错误的假设，关于sorted或可能关于在比较过程中如何处理元组和/或列表类型。

问题

1. sorted即使函数以这种方式改变了原始序列，为什么仍说它是“稳定的”？
2. 将默认行为设置为lambda版本的行为不会与“稳定”的含义更一致吗？为什么不这样设置？
3. 这种行为是否仅仅是元组和/或列表本质上比较的副作用（即错误假设）？

谢谢。

---

请注意，这是不是对默认的行为是否是或不是有用的，常见的，还是其他什么东西。这是关于默认行为是否与稳定意味着什么的定义一致（恕我直言，似乎并非如此）以及文档中提到的稳定性保证。

Answer 1

想一想 -(1, 2)来之前(1, 3)，不是吗？默认情况下对列表进行排序并不自动意味着“仅根据第一个元素对其进行排序”。否则，你可能会说，apple来之前aardvark在字母表。换句话说，这与稳定性无关。

文档也很好地解释了数据结构如lists 和tuples 如何按字典顺序排序：

特别是，元组和列表通过比较相应的元素按字典顺序进行比较。这意味着要比较相等，每个元素必须比较相等，并且两个序列必须具有相同的类型和相同的长度。

Answer 2

Stable sort keeps the order of those elements which are considered equal from the sorting point of view. Because tuples are compared element by element lexicographically, (1, 2) precedes (1, 3), so it should go first:

>>> (1, 2) < (1, 3)
True