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
>>> 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
>>> 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
>>> 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
>>> 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!

Hi, I'm Christoph Schiessl.

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.

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