Sorting is not comparing¶

Level: 201 · for Python programmers

One line: sorted() orders strings by code point, no human alphabet is ordered by code point, and the gap between those two facts is why a Polish name list comes back wrong.

This is the most useful bug in this chapter, because it produces output that is obviously wrong to a reader and completely invisible to a test suite written in English. Sort a list of Polish surnames with sorted() and every name carrying a diacritic is dumped at the bottom — Łukasiewicz after Zawadzki, which no Polish speaker would ever write and no ASCII test case would ever catch.

The cause is not a bug in sorted(). Python compares strings by comparing code points left to right, which is fast, total, and stable. It is simply not what any alphabet means by "alphabetical".

Verified output of sorting_is_not_comparing_py.py — regenerated by tools/run_examples.py, never hand-typed.

1. WHAT PYTHON DOES BY DEFAULT
   sorted() compares code points, left to right.

     Adamczyk
     Cieślak
     Lewandowski
     Nowak
     Sikora
     Zawadzki
     Ćwikła
     Łukasiewicz
     Śliwa
     Żeromski

2. WHY -- the code point is the whole explanation
     ord('L') =    76   ord('Ł') =   321   so 'Ł' > 'L' is True
     ord('Z') =    90   ord('Ż') =   379   so 'Ż' > 'Z' is True
     ord('S') =    83   ord('Ś') =   346   so 'Ś' > 'S' is True
     ord('C') =    67   ord('Ć') =   262   so 'Ć' > 'C' is True

     Every Polish letter with a diacritic sits above U+00FF, and every
     unaccented Latin letter sits below U+007B. So they ALL sort last.

3. WHAT POLISH ACTUALLY WANTS
   Ł belongs between L and M, not after Z.

     Adamczyk
     Cieślak
     Ćwikła
     Lewandowski
     Łukasiewicz
     Nowak
     Sikora
     Śliwa
     Zawadzki
     Żeromski

4. THE SORT KEY IS THE IDEA
   sorted(key=...) never compares the words -- it compares what the key
   returns. Here is what the key makes of two of them:

     Lewandowski    'l' 'e' 'w' 'a'      -> [14, 6, 27, 0] ...
     Łukasiewicz    'ł' 'u' 'k' 'a'      -> [15, 26, 13, 0] ...

     'l' is rank 14 and 'ł' is rank 15, so Lewandowski comes first --
     decided by the second element, exactly as tuple comparison works.

5. THE STDLIB ANSWER, AND WHY THIS PROGRAM CANNOT SHOW IT WORKING
   locale.strxfrm() asks the C library for a collation key. The C library
   knows the real rules -- but only for a locale that is INSTALLED, and
   this program runs under LC_ALL=C so that its output is the same on
   every machine. Under the C locale there are no rules to know:

     sorted(key=locale.strxfrm) == sorted()   True
     first three: ['Adamczyk', 'Cieślak', 'Lewandowski']

     That True is the whole warning. Under the C locale strxfrm gives
     back code-point order -- the wrong answer, silently, with the
     correct API. A container, a cron job and a CI runner all default
     to C or C.UTF-8, which is how 'it sorted fine on my laptop'
     becomes a bug report from Warsaw. Check what you are running
     under before trusting the call: locale -a | grep -i pl

6. A THIRD ANSWER THAT IS ALMOST RIGHT
   Stripping the diacritics sorts 'close enough' for a search box,
   and is wrong for a phone book -- it cannot tell ź from ż.

     Łukasiewicz    -> 'łukasiewicz'
     Żeromski       -> 'zeromski'
     Źróbek         -> 'zrobek'

     Note Ł survives: it is U+0141, a letter in its own right, with no
     combining mark to strip. NFD does not decompose it.

The three answers in that run are a genuine trade, not a ladder.

A hand-written key — rewriting each word as the positions of its letters in an alphabet you spell out — is reproducible on every machine, obvious to read, and easy to test. It is also yours to maintain, and it handles exactly one language. For a fixed domain (a Polish surname index, a Czech product list) that is often the right answer, and the program above is the whole implementation.

locale.strxfrm() hands the job to the C library, which knows the real rules — including the ones you would never think of, like Czech treating ch as a single letter between h and i, or French Canada ordering accents from the right. It is the correct answer, and it has a hard practical edge: it needs the locale to be installed, it is process-global state set by locale.setlocale(), and it is not thread-safe. The program above prints whether each locale exists rather than printing an order, precisely because the answer differs between machines — which is the same reason this library records answer keys from programs that cannot vary.

Stripping the diacritics is the one that feels clever and is usually wrong. It is fine for a search box, where you want zeromski to find Żeromski. It is wrong for anything ordered, because it cannot distinguish ź from ż — and note from the run that it does not even strip Ł, which is U+0141, a letter in its own right with no combining mark to remove. NFD decomposes ż into z plus a mark; it leaves Ł alone.

For the real thing, the answer is a library. The Unicode Collation Algorithm (UTS #10 ↗) is what strxfrm approximates and what PyICU ↗ implements properly, with per-locale tailoring you can select without touching global state. This library is stdlib-only by rule, so PyICU does not appear in an example here — but "use ICU" is the correct advice for a product, and pretending otherwise would be the sort of omission CONTRIBUTING forbids.

And the model underneath all three lives next door. UTS #10's answer is not one comparison but three, asked in order — base letters, then accents, then case — which is the vocabulary that makes "why is ł next to l but after it" answerable instead of merely observable. Sorting and collation ↗ in the encodings library owns that half: the three levels reproduced from a toy key with the standard's own weight table beside them, one nine-word list measured into five correct orders on three C libraries eight years apart, and the glibc 2.28 rewrite of that data — which invalidated PostgreSQL indexes worldwide and did it silently, because nothing could warn about a collation change until PostgreSQL 13.

One thing from that page belongs in a Python reader's head directly, because it is about sorted rather than about Unicode. A collation exists in order to ignore things, so it makes ties on purpose between strings that are not equal — and sorted is stable, which means a tie comes out in the order it went in. That is a promise about the algorithm, not about the answer: feed the same two rows in the other order and you get the other result, from the same correct key. Stability is not determinism, and the one-line fix is UTS #10's own — key=lambda s: (collate(s), s), falling through to the raw code points, which is the one ordering no locale tailors and no library version rewrites.

If you are coming from ABAP¶

SORT itab BY field uses the binary ordering of the internal representation, which is UTF-16 code units — the same class of answer as Python's, and wrong in the same way for the same reason. The SAP answer is a sort using a collation-aware comparison, and in practice much SAP code sidesteps it by sorting on a separate normalized key column, which is exactly the "hand-written key" strategy above with the key stored rather than computed. (Not machine-checked — CI cannot run ABAP.)

Try it¶

Add Źróbek to the list and sort it three ways. Where does it land under each, and which one matches the Polish alphabet — z, then ź, then ż?
Sort ["Chalupa", "Cukr", "Hora"] as Czech, where ch is one letter sorting after h. A per-character key cannot do this. What has to change about the key function?
Check whether pl_PL.UTF-8 exists on your machine with locale -a | grep -i pl. Then try the same inside docker run --rm -it ubuntu:24.04 and see how few locales a bare container has.

Sorting is not comparing¶

If you are coming from ABAP¶

Try it¶

See also¶