The Built-In sorted() Function

by Christoph Schiessl on Python

Sorting is one of the fundamental building blocks of many algorithms, and hence, Python's standard library includes several tools to make sorting easy and performant. The most basic of these tools is the built-in sorted(iterable, /, *, key=None, reverse=False) function, which takes an object implementing the iterable protocol as a position-only parameter and returns a new list object containing the same elements as the iterable, but in ascending order.

Many built-in types, including all collections, are iterable and can be used as input for sorted(). Note that the input object is never modified in place — even if it is a list, the sorted() function always returns a new list object and never modifies the input list.

Python 3.12.3 (main, Apr 20 2024, 16:22:09) [GCC 13.2.1 20230801] on linux
Type "help", "copyright", "credits" or "license" for more information.
>>> sorted([])         # empty iterable => empty list
[]
>>> sorted([2, 1, 3])  # lists are iterable
[1, 2, 3]
>>> sorted((2, 1, 3))  # tuples are iterable
[1, 2, 3]
>>> sorted({2, 1, 3})  # sets are also iterable
[1, 2, 3]
>>> l = [2, 1, 3]
>>> sorted(l) is not l # returns a new list object
True

One property of sorting, in general, is that the length of the input (i.e., the number of elements of the parameter) is always equal to the length of the output (i.e., the number of elements of the return value).

Stability

Another property of the sorted() function, in particular, is that it guarantees stability. One way to understand this property is that elements of the input parameter are collectively only moved by the minimal distance possible. Hence, equal elements maintain their positions relative to each other.

Python 3.12.3 (main, Apr 20 2024, 16:22:09) [GCC 13.2.1 20230801] on linux
Type "help", "copyright", "credits" or "license" for more information.
>>> class Foo:
...   def __init__(self, v: int) -> None:
...     self.v = v
...   def __repr__(self) -> str:
...     return f"Foo(v={self.v})"
...   def __lt__(self, other) -> bool:
...     return self.v < other.v
...
>>> a, b = Foo(3), Foo(3)
>>> assert a is not b
>>> input_list = [Foo(1), a, Foo(2), Foo(4), b, Foo(5)] # a before b
>>> (output_list := sorted(input_list))
[Foo(v=1), Foo(v=2), Foo(v=3), Foo(v=3), Foo(v=4), Foo(v=5)]
>>> assert output_list[2] is a and output_list[3] is b  # a still before b

Note I'm implementing the __lt__(self, other) method for the Foo class to allow "less than" comparisons of Foo objects. Basically, if you have two instances of the Foo class, a and b, and then compare them with a < b, it calls the method a.__lt__(b) in the background to determine if the expression evaluates to True or False.

Descending order with the reverse parameter

By default, sorted() returns a list with elements in ascending order (i.e., smallest element first and greatest element last). Suppose you want descending order (i.e., greatest element first and smallest element last). In that case, you can easily achieve this with the reverse keyword-only parameter.

Python 3.12.3 (main, Apr 20 2024, 16:22:09) [GCC 13.2.1 20230801] on linux
Type "help", "copyright", "credits" or "license" for more information.
>>> sorted([2, 1, 3])  # default value for reverse is False
[1, 2, 3]
>>> sorted([2, 1, 3], reverse=False)
[1, 2, 3]
>>> sorted([2, 1, 3], reverse=True)
[3, 2, 1]

Mapping with the key parameter

Lastly, there is key, also a keyword-only parameter that defaults to None. With this parameter, it's possible to map elements of the input parameter to other values for comparison. This parameter does not affect the elements in the return value; instead, it temporarily maps these elements to other values to achieve a different ordering.

In the example above, I had to implement the __lt__() method to make Foo objects comparable. This implementation was very straightforward because it essentially delegated comparisons to the v attribute of Foo objects. The same behavior can be achieved with the key parameters and a lambda function to map Foo objects to their respective v attributes.

Python 3.12.3 (main, Apr 20 2024, 16:22:09) [GCC 13.2.1 20230801] on linux
Type "help", "copyright", "credits" or "license" for more information.
>>> class Foo:
...   def __init__(self, v: int) -> None:
...     self.v = v
...   def __repr__(self) -> str:
...     return f"Foo(v={self.v})"
...
>>> input_list = [Foo(1), Foo(3), Foo(2), Foo(4), Foo(3), Foo(5)]
>>> sorted(input_list, key=lambda foo: foo.v)
[Foo(v=1), Foo(v=2), Foo(v=3), Foo(v=3), Foo(v=4), Foo(v=5)]

Thank you very much for reading, and see you again soon!

Christoph Schiessl

Hi, I'm Christoph Schiessl.

I help you build robust and fast Web Applications.


I'm available for hire as a freelance web developer, so you can take advantage of my more than a decade of experience working on many projects across several industries. Most of my clients are building web-based SaaS applications in a B2B context and depend on my expertise in various capacities.

More often than not, my involvement includes hands-on development work using technologies like Python, JavaScript, and PostgreSQL. Furthermore, if you already have an established team, I can support you as a technical product manager with a passion for simplifying complex processes. Lastly, I'm an avid writer and educator who takes pride in breaking technical concepts down into the simplest possible terms.

Continue Reading?

Here are a few more Articles for you ...


Function Definition Basics

Explore Python's function definition statement and discover its features with this series of articles. Get started with this simple introduction.

By Christoph Schiessl on Python

Function Definition with Simple Parameters

Learn about functions with simple parameters in Python, including how the called can decide to use positional or keyword notation.

By Christoph Schiessl on Python

Function Definition with Catch-All Parameters

Learn how to use catch-all parameters in Python functions with this guide. Capture excess positional and keyword arguments to make your functions more flexible.

By Christoph Schiessl on Python

Web App Reverse Checklist

Ready to Build Your Next Web App?

Get my Web App Reverse Checklist first ...


Software Engineering is often driven by fashion, but swimming with the current is rarely the best choice. In addition to knowing what to do, it's equally important to know what not to do. And this is precisely what my free Web App Reverse Checklist will help you with.

Subscribe below to get your free copy of my Reverse Checklist delivered to your inbox. Afterward, you can expect one weekly email on building resilient Web Applications using Python, JavaScript, and PostgreSQL.

By the way, it goes without saying that I'm not sharing your email address with anyone, and you're free to unsubscribe at any time. No spam. No commitments. No questions asked.