11

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?

4

1 回答 1

26

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.

于 2019-01-22T04:50:10.863 回答