Is python's sorted () function a guarantee of stability?

Question

The documentation does not guarantee this. Is there any other place where it is documented?

I assume that it can be stable, since the sorting method in lists is guaranteed to be stable (Notes 9th paragraph: “Starting with Python 2.3, the sort () method is guaranteed to be stable”), and the sorted one is functionally similar. However, I cannot find any definitive source that says so.

Purpose: I need to sort based on the primary key as well as the secondary key in cases where the primary key is equal in both records. If sorted () is guaranteed to be stable, I can sort by a secondary key, and then sort by the first key and get the result I need.

PS: To avoid confusion, I use a stable value in the sense of "sorting is stable if it does not allow you to change the relative order of elements comparing the same ones."

Answer 1

Yes, the intent of the manual really ensures that sorted is stable and, indeed, uses the same algorithm as the sort method. I really understand that the documents are not 100% clear about this certificate; doc patches are always welcome!

Answer 2

They are stable .

By the way: sometimes you can ignore the knowledge of whether sorting and sorting are stable by combining multi-pass sorting in a single-pass.

For example, if you want to sort objects based on their attributes last_name , first_name , you can do this in one go:

 sorted_list= sorted( your_sequence_of_items, key= lambda item: (item.last_name, item.first_name)) 

using tuple comparison.

This answer, as is, covers the original question. For further questions related to sorting, there is a Python sorting instruction .

Answer 3

At the same time, the documentation has changed ( corresponding commit ), and the current documentation, sorted explicitly, guarantees:

The built-in sorted() function is guaranteed to be stable. A variety is stable if it does not allow changing the relative order of elements being compared equal - this is useful for sorting in several passes (for example, sorting by department, then by salary class).

This piece of documentation was added in Python 2.7 and Python 3.4 (+), so any compatible implementation of this language version should have stable sorted .

Please note that for CPython list.sort been stable since Python 2.3

• Tim Peters rewrote his implementation of list.sort() - this is "stable sorting" (equal inputs appear in the same order in the output) and faster than before.

I'm not 100% sorted , currently it just uses list.sort , but I have not checked the history for this. But most likely, he "always" used list.sort .

Answer 4

The "What New" docs for Python 2.4 effectively determine that sorted () first creates a list and then calls sort () on it, giving you the necessary guarantee, but not in the "official" docs. You can also just check the source if you are really worried.

Answer 5

The Python 3.6 document now says for sorting that

Varieties are guaranteed stable

In addition, this document has a reference to the stable Timsort , which states that

Timsort has been the standard Python sorting algorithm since version 2.3