Optimize Python Sorting with One Little Trick

Aliaksandr Valshtein — Wed, 19 Nov 2025 20:54:23 +0000

TL;DR

# if we have a class like this
from dataclasses import dataclass

@dataclass(order=True)
class Item:
    name: str
    quantity: int

# in a big enough list
items = [Item("book", 5), Item("pencil", 3), Item("book", 6), ...]

# this sorting will be faster
items.sort(key=lambda item: (item.name, item.quantity))
# than this
items.sort()

Why? Well...

One of the things Python makes really simple is sorting.

You can easily find the answer to the question "how sorting is implemented in Python?" which almost always answers another question: "What sorting algorithm does Python use?".

The answer often leaves one detail behind. An optimization introduced in python 3.7:

sorted() and list.sort() have been optimized for common cases to be up to 40-75% faster. (Contributed by Elliot Gorokhovsky in bpo-28685.)

But before we dig into that...

Brief Re-introduction to Sorting in Python

If you want to sort a list in python, you have two options:

A list method: list.sort(*, key=None, reverse=False), which sorts the given list in-place
A built-in function: sorted(iterable, /, *, key=None, reverse=False), which returns a sorted list without modifying its argument

For any other built-in iterable, you can only use sorted.

sorted always returns a list because it uses list.sort internally.

Here is a rough equivalent of CPython's sorted C implementation rewritten in pure python:

def sorted(iterable: Iterable[Any], key=None, reverse=False):
    new_list = list(iterable)
    new_list.sort(key=key, reverse=reverse)
    return new_list

Yes, it's that simple.

How Python Makes Sorting Faster

As Python's internal documentation for sorting puts it:

It is sometimes possible to substitute faster type-specific comparisons for the slower, generic PyObject_RichCompareBool

And in short this optimization can be described as follows:

When a list is homogeneous, Python uses type-specific comparison function

What Is a Homogeneous List?

A homogeneous list is a list that contains elements only of one type.

For example:

homogeneous = [1, 2, 3, 4]

On the other hand, this is not a homogeneous list:

heterogeneous = [1, "2", (3, ), {'4': 4}]

Official Python tutorial also mentions the difference:

Lists are mutable, and their elements are usually homogeneous and are accessed by iterating over the list

A side note about tuples

That same tutorial states:

Tuples are immutable, and usually contain a heterogeneous sequence of elements

So if you ever wonder when to use a tuple or a list here's a rule of thumb: If the elements are of the same type, use a list. Otherwise use a tuple.

Wait, and what about `array`s ?

Python implements a homogeneous array container object for numeric values.

However, as of python 3.14, arrays do not implement their own sort method.

The only way to sort them is by using sorted, which internally creates a list out of the array, erasing any type-related information in the process.

Why Using Type-Specific Comparison Function Helps?

Comparisons in python are costly, because Python performs various checks before doing any actual comparison.

Here is a simplified explanation of what happens under the hood when you compare two values in python:

Python checks that the values passed to comparison function are not NULL
If values are of different types, but right operand is a subtype of the left, Python uses right operand's comparison function, but reversed (e.g., it will use < for >)
If the values are of the same type, or different types but neither is a subtype of the other:
- Python will first try left operand's comparison function
- If that fails, it will try right operand's comparison function, but reversed.
- If that fails too, and the comparison is for equality or inequality, it will return identity comparison (True for values that refer to the same object in memory)
- Otherwise, it raises TypeError

On top of this, each type's own comparison functions implement additional checks.

For example, when comparing strings, Python will check if the string characters take more than one byte of memory, and float comparison will compare a pair of float's and a float and an int differently.

A more detailed explanation and diagram can be found here: Adding Data-Aware Sort Optimizations to CPython

Before this optimization was introduced, Python had to execute all this various type-specific and non-type-specific checks every time two values were compared during sorting.

Checking List Element's Types in Advance

There's no magical way to know if all the elements of a list are of the same type other than to iterate over the list and check each element.

Python does almost exactly that — checking the types of sorting keys generated by key function passed to list.sort or sorted as a parameter

Constructing a List of Keys

If a key function is provided, Python uses it to construct a list of keys, otherwise it uses the list's own values as sorting keys.

In an oversimplified manner, keys construction can be expressed as the following python code.

if key is None:
    keys = list_items
else:
    keys = [key(list_item) for list_item in list_item]

Note, that keys used internally in CPython are a C array of CPython object references, and not a Python list

Once the keys are constructed, Python checks their types.

Checking Key's Type

When checking the types of keys, Python's sorting algorithm tries to determine if all elements in the keys array are either str, int, float or tuple, or simply of the same type, with some constraints for base types.

It's worth noting that checking the types of the keys adds some extra work up front. Python does this because it usually pays off by making the actual sorting faster, especially for longer lists.

`int` constraints

int should not be a bignum

Practically this means that for this optimization to work, integer should be less than 2^30 - 1 (this may vary depending on the platform)

As a side note, here is a great article which explains how Python handles big integers: # How python implements super long integers?

`str` constraints

All characters of a string should take less than 1 byte of memory, meaning that they should be represented by integer values in the range of 0-255

In practice, this means that strings should consist only of Latin characters, spaces, and some special characters found in the ASCII table.

`float` constraints

There are no constraints for floats in order for this optimization to work.

`tuple` constraints

Only the first element's type is checked
This element itself should not be a tuple itself
If all tuples share the same type for their first element, the comparison optimization is applied to them
All other elements are compared as usual

How Can I Apply This Knowledge?

First of all, isn’t it fascinating to know?

Secondly, mentioning this knowledge could be a nice touch in a Python Developer interview.

As for actual code development, understanding this optimization can help you improve sorting performance.

Optimize by Selecting the Type of Values Wisely

According to the benchmark in the PR that introduced this optimization, sorting a list that consists only of floats rather than a list of floats with even a single integer at the end is almost twice as fast.

So when it's time to optimize, transforming list like this

floats_and_int = [1.0, -1.0, -0.5, 3]

Into list that looks like this

just_floats = [1.0, -1.0, -0.5, 3.0] # note that 3.0 is a float now

might improve performance.

Optimize by Using Keys for Lists of Objects

While Python's sorting optimization works well with built-in types, it's important to understand how it interacts with custom classes.

When sorting objects of custom classes, Python relies on the comparison methods you define, such as __lt__ (less than) or __gt__ (greater than).

However, the type-specific optimization doesn't apply to custom classes.
Python will always use the general comparison method for these objects.

Here's an example:

class MyClass:
    def __init__(self, value): 
        self.value = value 

    def __lt__(self, other): 
        return self.value < other.value 

my_list = [MyClass(3), MyClass(1), MyClass(2)] 
sorted_list = sorted(my_list)

In this case, Python will use the __lt__ method for comparisons, but it won't benefit from the type-specific optimization. The sorting will still work correctly, but it may not be as fast as sorting built-in types.

If performance is critical when sorting custom objects, consider using a key function that returns a built-in type:

sorted_list = sorted(my_list, key=lambda x: x.value)

Afterword

Premature optimization, especially in Python, is evil.

You should not design your entire application around specific optimizations in CPython, but it’s good to be aware of these optimizations: knowing your tools well is a way of becoming a more skilled developer.

Being mindful of optimizations like these allows you to take advantage of them when the situation calls for it, especially when performance becomes critical:

Consider a scenario where were your sorting is based on timestamps: using a homogeneous list of integers (Unix timestamps) instead of datetime objects could leverage this optimization effectively.

However, it's crucial to remember that code readability and maintainability should take precedence over such optimizations.

While it's important to know about these low-level details, it is as much important to appreciate Python's high-level abstractions that make it such a productive language.

Git Extension to handle multiple repositories easily

Aliaksandr Valshtein — Fri, 09 Feb 2024 15:21:07 +0000

The sad reality of software development is that not everyone uses git submodules, and dealing with multiple interconnected repositories can be tedious.

Naturally, a whole class of git extensions exists to solve this problem.

None of them suited me, so I created my own!

Generally, it's a good idea to use submodules or subtrees, but usually whether to use it or not is not up to you.

So I came up with a simple git extension to handle multiple repositories in bulk.

I present to you git-all

Let's assume that you have the following directory structure

my-awesome-repositories/
    my-awesome-repo-1/ # this is a git repository
    my-awesome-repo-2/ # that's another git repository

Executing git all status inside my-awesome-repositories directory is the exact equivalent of executing the following bash commands:

cd my-awesome-repo-1
git status
cd ..

cd my-awesome-repo-2
git status
cd ..

What can I do with it?

Whatever you want! Generally, almost everything you type after all will be passed to git unchanged.

The syntax is git all {basically any other git command}

Basically, you can do whatever git can do.

A couple of examples:

git all tag -a v1 -m "release" — this command tags all commits of every repository in the current subfolder with v1 tag and "release" tag message
git all push origin master — this one will push from all repositories in the current subfolder to branch master on the origin remote

What about cloning?

The only different thing about git all is cloning, but, instead of repository name you just need to provide a file where every line is an argument to regular git clone, and that's all (pun intended).

$ cat myrepo.list
--branch master https://github.com/stencila/test.git 
https://github.com/rtyley/small-test-repo.git
$ git all clone myrepo.list

How it's different from similar extensions?

It's just a simple bash script, similar to one you could have written yourself
It's zero-configuration, you don't need to register directories, create workspaces and configuration files
It's written in bash, so you don't need to use Node.js or python
You don't need to learn how to use it, it's just your regular git commands

DEV Community: Aliaksandr Valshtein