Is python's sorted() function guaranteed to be stable?

python sorted stable-sort
sundar - Reinstate Monica picture sundar - Reinstate Monica · Dec 16, 2009 · Viewed 30.8k times · Source

The documentation doesn't guarantee that. Is there any other place that it is documented?

I'm guessing it might be stable since the sort method on lists is guaranteed to be stable (Notes 9th point: "Starting with Python 2.3, the sort() method is guaranteed to be stable"), and sorted is functionally similar. However, I'm not able to find any definitive source that says so.

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

PS: To avoid any confusion, I'm using stable in the sense of "a sort is stable if it guarantees not to change the relative order of elements that compare equal".

Answer

Alex Martelli picture Alex Martelli · Dec 16, 2009

Yes, the intention of the manual is indeed to guarantee that sorted is stable and indeed that it uses exactly the same algorithm as the sort method. I do realize that the docs aren't 100% clear about this identity; doc patches are always happily accepted!

Related questions

How to get indices of a sorted array in Python

I have a numerical list: myList = [1, 2, 3, 100, 5] Now if I sort this list to obtain [1, 2, 3, 5, 100]. What I want is the indices of the elements from the original list in the sorted order i.e. [0, 1, 2, 4, 3] --- ala MATLAB's sort function that returns …

Read More
Insert an item into sorted list in Python

I'm creating a class where one of the methods inserts a new item into the sorted list. The item is inserted in the corrected (sorted) position in the sorted list. I'm not allowed to use any built-in list functions or …

Read More
Sort list of strings alphabetically

So i have a question, how can i sort this list: ['Pera','mela','arancia','UVA'] to be like this: ['arancia','mela','Pera','UVA'] In the exercise it said to use the sorted() function with the cmp argument.

Read More