The Built-In sorted() Function

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!