ordering of sorted() when ties are present

Question

Consider this simple example

x = [1,2,3,4]
y = [1,2,2,4]

The code below returns a tuple containing elements from x and y sorted by decreasing order of the number in y list.

sorted(zip(x,y), key = lambda x: x[1], reverse = True)
Out[10]: [(4, 4), (2, 2), (3, 2), (1, 1)]

My question is: you can see that the tuple (2,2) and (3,2) are essentially tied (same y value = 2), yet one has to pick which one will come first in the sorted list.

What is the default rule for that? Does Python keep the elements in the original order by default?

Thanks!

Answer 1

See Sort Stability and Complex Sorts in Sorting HOWTO:

Sorts are guaranteed to be stable. That means that when multiple records have the same key, their original order is preserved.

Answer 2

Yes, from the docs

The built-in sorted() function is guaranteed to be stable. A sort is stable if it guarantees not to change the relative order of elements that compare equal — this is helpful for sorting in multiple passes (for example, sort by department, then by salary grade).

The keyword for this is stable, as indicated from the quote above: A sort is stable if it preserves the original order when there are ties in the sort order, and Python sorts are guaranteed to be stable.