Python 3 list sorting with a tie-breaker

Question

I have seen a lot of similar questions here but none of them so far have answered the question directly, but instead have provided work arounds in specific scenarios to the asker's problem.

I would like a general answer to the question of breaking ties in Python's Timsort. Can it be done? If it can be done, what is the general method of doing that.

For example take the list of tuples

>>> tuples = [(2,1), (2,9), (3, 8), (1,3), (1,2), (1,1)]

I want to sort these tuples such that their order is determined primarily by the value of the first value in each tuple. If we leave reversed=False, then they will be sorted by increasing order. I would do this with the following

>>> tuples.sort(key=lambda t: t[0])

The result will be

>>> tuples
[(1,3), (1,2), (1,1), (2,1), (2,9), (3, 8)]

The question is what can I do general to break the tie between the first three elements. I would like to know if this is generally possible and applicable in any problem where defining a sort key comes up.

Most of the time the other answers will mention that Timsort is stable. Does this rule imply that it is not possible to break ties?

Aglet

You mean tuples.sort()? Comparisons on tuples work the way you seem to want. (If you don’t actually have a list of tuples, your key function can return a tuple.) – Urias

Stable means the original order is retained in the event of a tie. You can still create a key with a tie-breaker factor so that actual ties become impossible. – Rowan

Answer 1

As I understand it you would like to sort on the initial value first and then sort on the second tuple value without losing the initial sorted list.

try this

tuples.sort(key=lambda x: (x[0], x[1]))

In this case x[0] and x[1] are the primary and secondary sorting key respectively. Hope this helps.

Kowatch

This is the default action without including a key parameter at all. – Rowan

That is very good to know. Thanks for the comment. I suppose it is only useful then if you wanted to a series of sorts on a sequence that did not match the order of the values in the tuple. – Kowatch