Introduction

It all started with a short script meant to combine information about addresses e-mail of employees, obtained from a mailing list of users, with the positions of employees obtained from the HR database. Both lists were exported to text files in Unicode encoding UTF-8 and saved with Unix line endings.

Contents mail.txt

Ivanov Andrey;ia@example.com

Contents buhg.txt

Ivanova Alla;painter
Yolkina Ella;crane operator
Ivanov Andrey;locksmith
Abakanov Mikhail;painter

To merge, the files were sorted using a Unix command sort and fed into a Unix program join, which unexpectedly terminated with an error:

$> sort buhg.txt > buhg.srt
$> sort mail.txt > mail.srt
$> join buhg.srt mail.srt > result
join: buhg.srt:4: is not sorted: Ivanov Andrey;locksmith

Viewing the sorting result visually showed that overall, the sorting was correct, but in the case of matching male and female surnames, females were placed before males:

$> sort buhg.txt
Abakanov Mikhail;painter
Yolkina Ella;crane operator
Ivanova Alla;painter
Ivanov Andrey;locksmith

Looks like a glitch in Unicode sorting or a manifestation of feminism in the sorting algorithm. The former, of course, is more plausible.

Let's put that aside for now join and focus on sort. Let's try to solve the problem by trial and error. To start, we will change the locale from en_US to ru_RU. For sorting, it would be sufficient to set the environment variable LC_COLLATE, but we won't be petty:

$> LANG=ru_RU.UTF-8 sort buhg.txt
Abakanov Mikhail;painter
Yolkina Ella;crane operator
Ivanova Alla;painter
Ivanov Andrey;locksmith

Nothing changed.

Let's try to re-encode the files into a single-byte encoding:

$> iconv -f UTF-8 -t KOI8-R buhg.txt 
 | LANG=ru_RU.KOI8-R sort 
 | iconv -f KOI8-R -t UTF8

Again, nothing changed.

Nothing can be done, we'll have to search for a solution on the internet. There’s nothing specific about Russian surnames, but there are questions about other sorting oddities. Here’s an example of such a problem: unix sort treats ‘-‘ (dash) characters as invisible. In short, the strings "a-b", "aa", "ac" are sorted as "aa", "a-b", "ac".

The standard answer everywhere is: use the programmer's locale "C" and you will be happy. Let's try it:

$> LANG=C sort buhg.txt
Yolkina Ella;crane operator
Abakanov Mikhail;painter
Ivanov Andrey;locksmith
Ivanova Alla;lawyer

Something has changed. The Ivanovs lined up in the correct order, but Yolkina slid somewhere. Let's return to the original task:

$> LANG=C sort buhg.txt > buhg.srt
$> LANG=C sort mail.txt > mail.srt
$> LANG=C join buhg.srt mail.srt > result

It worked without errors, just as the internet promised. Despite the inclusion of Elkin in the first line.

The problem seems to be resolved, but just in case, let's try another Russian encoding — Windows encoding. CP1251:

$> iconv -f UTF-8 -t CP1251 buhg.txt 
 | LANG=ru_RU.CP1251 sort 
 | iconv -f CP1251 -t UTF8

The sorting result, surprisingly, will match the locale. "C", and the entire example, accordingly, passes without errors. It's some kind of mysticism.

I don't like mysticism in programming, as it usually hides errors. I will have to seriously address how it works sort and what it affects. LC_COLLATE .

In the end, I will try to answer questions:

why women's surnames were sorted incorrectly.
why LANG=ru_RU.CP1251 turned out to be equivalent. LANG=C
why there are sort and join different representations of the order of sorted lines.
why all my examples have errors.
finally, how to sort strings to my liking.

Sorting in Unicode.

The first stop will be technical report No. 10 titled Unicode collation algorithm. on the website unicode.org. The report contains many technical details, so I'll allow myself to provide a summary of the main ideas.

Collation — "comparison" of strings — is the basis of any sorting algorithm. The algorithms themselves may differ ("bubble", "merge", "quick"), but they all will use comparison of string pairs to determine their order.

Sorting strings in natural language is quite a complex issue. Even in the simplest single-byte encodings, the order of letters in an alphabet that differs from the English Latin alphabet won’t match the order of the numeric values that encode those letters. Thus, in the German alphabet, the letter Ö comes between O and P, while in the encoding CP850 it falls between ÿ and Ü..

One can attempt to abstract away from a specific encoding and consider “ideal” letters, which are arranged in a certain order, as is done in Unicode. Encodings UTF8, UTF16 or single-byte KOI8-R (if a limited subset of Unicode is needed) will yield different numeric representations of letters, while still referring to the same elements of the base table.

It turns out that even by building a character table from scratch, we cannot assign a universal order to the characters. In various national alphabets that use the same letters, the order of those letters may differ. For example, in the French language, Æ will be considered a ligature and sorted as a string. AEIn Norwegian, however, Æ will be a separate letter, which is placed after Z. By the way, besides ligatures like Æ there are letters represented by multiple symbols. For instance, in the Czech alphabet, there is the letter Ch, which stands between H and I.

In addition to differences in alphabets, there are also other national traditions that influence sorting. In particular, the question arises: in what order should words consisting of uppercase and lowercase letters follow in a dictionary? Additionally, punctuation marks can affect sorting. In Spanish, an inverted question mark is placed at the beginning of a question (¿Te gusta la música?). In this case, it is obvious that questions should not be grouped into a separate cluster outside the alphabet, but how should strings with other punctuation marks be sorted?

I will not dwell on string sorting in languages that differ significantly from European ones. It is worth noting that in languages written from right to left or top to bottom, characters in strings are likely stored in reading order, and even in non-alphabetic scripts, there are ways to order strings character by character. For example, hieroglyphs can be ordered by stroke (the keys of Chinese characters) or by pronunciation. How emojis should be ordered, to be honest, I have no idea, but something can certainly be devised for them.

Based on the aforementioned features, the main requirements for comparing strings based on Unicode tables were formulated:

string comparison does not depend on the position of characters in the code table;
sequences of characters that form a single character are brought to their canonical form (A + the upper circle is the same as Å);
); in string comparison, a character is considered in the context of the string and, if necessary, is combined with neighbors into a single comparison unit (Ch in Czech) or split into several (Æ in French);
All national features (alphabet, uppercase/lowercase letters, punctuation, order of writing styles) must be configurable down to manually assigning order (emoji);
Comparison is important not only for sorting but also in many other places, for example, for defining the range of rows (substitution {A… z} in bash);
comparison must be performed quickly enough.

Moreover, the authors of the report formulated comparison properties that algorithm developers should not rely on:

the comparison algorithm should not require a separate set of characters for each language (Russian and Ukrainian languages share most Cyrillic characters);
comparison should not be based on the order of characters in Unicode tables;
the weight of a string should not be an attribute of the string, as the same string in different cultural contexts can have different weights;
the weights of strings can change upon merging or splitting (from x < y it does not imply that xz < yz);
different strings with the same weights are considered equal from the sorting algorithm's perspective. Introducing additional ordering for such strings is possible, but it may degrade performance;
in repeated sorts, strings with the same weights may swap places. Stability is a property of a specific sorting algorithm, not of the string comparison algorithm (see the previous point);
sorting rules may change over time as cultural traditions are refined/modified.

It is also stated that the comparison algorithm is unaware of the semantics of the processed strings. For instance, strings consisting only of digits should not be compared as numbers, and articles should not be removed from lists of English names (Beatles, The).

To meet all the specified requirements, a multi-level (essentially four-level) table sorting algorithm is proposed.

Firstly, characters in the string are converted to their canonical form and grouped into comparison units. Each comparison unit is assigned several weights corresponding to different levels of comparison. The weights of comparison units are elements of ordered sets (in this case, integers) that can be compared greater than-less than. A special value IGNORED (0x0) indicates that this unit does not participate in comparison at the corresponding level. String comparisons may be repeated several times, using the weights of the relevant levels. At each of these levels, the weights of the comparison units of the two strings are sequentially compared to each other.

In various implementations of the algorithm for different national traditions, the coefficient values may differ, but the Unicode standard includes a basic weight table — "Default Unicode Collation Element Table" (DUCET). I would like to note that setting the variable LC_COLLATE actually serves as an indication for choosing the weight table in the string comparison function.

Weight coefficients DUCET are structured as follows:

at the first level, all letters are brought to a single case, diacritical marks are discarded, and punctuation marks (not all) are ignored;
at the second level, only diacritical marks are considered;
at the third level, only case is taken into account;
at the fourth level, only punctuation marks are taken into account.

Comparison occurs in several passes: first, the first level coefficients are compared; if the weights match, a reconsideration with the second level weights follows; then, possibly, the third and fourth levels.

Comparison ends when corresponding comparison units with different weights exist in the strings. Strings that have equal weights at all four levels are considered equal to each other.

This algorithm (with a lot of additional technical details) gave its name to report No. 10 — "Unicode Collation Algorithm" (UCA).

At this point, the sorting behavior from our example becomes a bit clearer. It would be good to compare it with the Unicode standard.

For testing implementations UCA there is a special test, which uses a weight file, implementing DUCET. In the weight file, you can find various curiosities. For example, it includes the order of Mahjong tiles and European dominoes, as well as the order of suits in a deck of cards (symbol 1F000 and beyond). The card suits are arranged according to bridge rules — ♣♦♥♠, and the cards within each suit are in the sequence 10, 2, 3… K.

Manually verifying the correctness of string sorting according to DUCET would be quite tedious, but fortunately for us, there exists an exemplary implementation of the library for working with Unicode — "International Components for Unicode" (ICU).

On the website of this library, developed in IBM, there are demo pages, including the string comparison algorithm page. We input our test strings with the default settings and, oh miracle, we get perfect Russian sorting.

Abakanov Mikhail; painter
Yolkina Ella; crane operator
Ivanov Andrey; plumber
Ivanova Alla; lawyer

By the way, on the website ICU you can find clarifications about the algorithm's operation when processing punctuation marks. In the examples Collation FAQ apostrophes and hyphens are ignored.

Unicode helped us, but to find the reasons for the strange behavior sort downward API support (simultaneously with this in Linux we'll have to look elsewhere.

Sorting in glibc

A quick look at the source codes of the utility sort from GNU Core Utils showed that the localization in the utility comes down to printing the current value of the variable LC_COLLATE when running in debug mode:

$ sort --debug buhg.txt > buhg.srt
sort: using ‘en_US.UTF8’ sorting rules

String comparison is performed by the standard function strcoll, meaning all the interesting stuff is in the library glibc.

At wiki project glibc dedicated to string comparison has one paragraph. From this paragraph, we can understand that the glibc sorting is based on the algorithm we already know, UCA (The Unicode collation algorithm) and/or on a closely related standard ISO 14651 (International string ordering and comparison). Regarding the latter standard, it should be noted that on the website standards.iso.org ISO 14651 it is officially declared public, but the corresponding link leads to a nonexistent page. Google returns several pages with links to official sites offering to purchase an electronic copy of the standard for a hundred euros, but on the third or fourth page of the search results, there are also direct links to PDF. Overall, the standard is practically indistinguishable from UCA, but it reads more boringly since it lacks vivid examples of national peculiarities of string sorting.

The most interesting information at wiki was a link to the bug tracker discussing the implementation of string comparison in glibc. From the discussion, one can learn that in glibc for string comparison a ISOtemplate table is used The Common Template Table (CTT), whose address can be found in the appendix A of the standard ISO 14651. Between 2000 and 2015, this table in glibc did not have a maintainer and was quite different (at least externally) from the current version of the standard. From 2015 to 2018, there was an adaptation to the new version of the table, and at present, you have the chance to encounter both the new version of the table (CentOS 8), as well as the old version (CentOS 7).

Now that we have all the information about the algorithm and auxiliary tables, we can return to the original problem and understand how to properly sort strings in the Russian locale.

ISO 14651/14652

The source code of the table we are interested in CTT is located in the majority of distributions Linux in the directory /usr/share/i18n/locales/. The table itself is located in the file iso14651_t1_common. Then this file is included in the file by the directive copy iso14651_t1_common which, in turn, is included in the national files, including in . In most distributionsall source files are included in the basic installation, but if they are not available, you will have to install an additional package from the distribution. en_US and ru_RUmay seem terribly verbose, with non-obvious rules for naming conventions, but if you break it down, it's quite simple. The structure is described in the standard Linux ISO 14652

File Structure . In most distributions , a copy of which can be downloaded from the website open-std.org. Another description of the file format can be read in OpenGroup. As an alternative to reading the standard, you can study the source texts of the function the specifications POSIX from collate_readglibc/locale/programs/ld-collate.c The file structure looks as follows: downward API support (simultaneously with this in By default, the symbol is used as the escape character, and the end of the line after the # symbol is a comment. Both characters can be overridden, which has been done in the new version of the table:.

escape_char / comment_char %

In the file, there will be tokens in the format

escape_char / comment_char %

The file will contain tokens in the format — a hexadecimal digit). This is the hexadecimal representation of the Unicode code points in the or UCS-4 (where x UTF-32 ). All other elements in angle brackets (including (UTF-32). All other elements in angle brackets (including and similar), are considered plain string constants, having no special meaning outside of context., indicates that the following contains data describing string comparisons. First, the names for the weights in the comparison table and the names for symbol combinations are specified. Generally speaking, the two types of names belong to two different entities, but in the actual file, they are mixed. The names for weights are defined by the keyword

Line LC_COLLATE collating-symbol

First, names for the weights in the comparison table and names for combinations of characters are set. Generally speaking, two types of names belong to two different entities, but in the actual file, they are mixed. Weight names are specified with the keyword collating-symbol (comparison character), since when comparing Unicode characters with the same weights, they will be considered equivalent characters.

The total length of the section in the current revision of the file is about 900 lines. I pulled examples from several places to show the arbitrariness of names and some types of syntax.

LC_COLLATE

collating-symbol 
collating-symbol 
collating-symbol 
collating-symbol 
...
collating-symbol 
collating-symbol 
collating-symbol 
...
collating-symbol ..
collating-symbol  % Guaranteed largest symbol value. Keep at end of this list
...
collating-element  from ""
collating-element  from ""

collating-symbol registers a string OSMANYA in the weight names table
collating-symbol .. registers a sequence of names consisting of a prefix S and a hexadecimal numeric suffix from 1D000 up to 1D35F.
FFFF downward API support (simultaneously with this in collating-symbol looks like a large unsigned integer in hexadecimal notation, but <SFFFF> is just a name that could look like <VERYBIGVAL>
name <U0413> means a code point in the encoding ). All other elements in angle brackets (including
collating-element from "" registers a new name for a pair of Unicode points.

When weight names are defined, the weights themselves are assigned. Since in comparison only greater-less relationships matter, weights are determined by a simple sequence of naming. Lighter weights are listed first, followed by heavier ones. I remind you that each Unicode character is assigned four different weights. Here, they are consolidated into a single ordered sequence. Theoretically, any symbolic name can be used at any of the four levels, but comments indicate that developers mentally separate names by levels.

% Symbolic weight assignments

% Third-level weight assignments




...
% Second-level weight assignments

 % COMBINING LOW LINE
 % COMBINING COMMA ABOVE
 % COMBINING REVERSED COMMA ABOVE
...
% First-level weight assignments
 % HORIZONTAL TABULATION 
 % LINE FEED
 % VERTICAL TABULATION
...
 % CYRILLIC SMALL LETTER DE
 % CYRILLIC SMALL LETTER KOMI DE
 % CYRILLIC SMALL LETTER DJE
 % CYRILLIC SMALL LETTER KOMI DJE
 % CYRILLIC SMALL LETTER GJE
 % CYRILLIC SMALL LETTER ZE WITH DESCENDER
 % CYRILLIC SMALL LETTER IE
 % CYRILLIC SMALL LETTER IE WITH BREVE
 % CYRILLIC SMALL LETTER UKRAINIAN IE
 % CYRILLIC SMALL LETTER ZHE

Finally, the actual weight table.

The weight section is enclosed in rows with keywords. order_start and order_end. Additional parameters order_start determine the direction in which rows are viewed at each comparison level. By default, the parameter forward. The body of the section consists of rows that contain a character code and its four weights. The character code can be represented by the character itself, a code point, or a symbolic name defined earlier. Weights can also be specified by symbolic names, code points, or the characters themselves. If code points or symbols are used, their weight corresponds to the numeric value of the code point (the position in the Unicode table). Characters not explicitly specified (as I understand) are considered appended in the table with a primary weight that matches their position in the Unicode table. A special weight value IGNORE means that at the corresponding comparison level, this character is ignored.

To demonstrate the weight structure, I selected three quite obvious fragments:

characters that are completely ignored
characters equivalent to the digit three at the first two levels
the beginning of the Cyrillic alphabet, which does not contain diacritics and is therefore sorted mainly by the first and third levels.

order_start forward;forward;forward;forward,position
 IGNORE;IGNORE;IGNORE;IGNORE % NULL (in 6429)
 IGNORE;IGNORE;IGNORE;IGNORE % START OF HEADING (in 6429)
 IGNORE;IGNORE;IGNORE;IGNORE % START OF TEXT (in 6429)
...
 ;;; % DIGIT THREE
 ;;; % FULLWIDTH DIGIT THREE
 ;;; % PARENTHESIZED DIGIT THREE
 ;;; % DIGIT THREE FULL STOP
 ;;; % MATHEMATICAL BOLD DIGIT THREE
...
 ;;; % CYRILLIC SMALL LETTER A
 ;;; % CYRILLIC CAPITAL LETTER A
 ;;; % CYRILLIC SMALL LETTER A WITH BREVE
 ;;; % CYRILLIC SMALL LETTER A WITH BREVE
...
 ;;; % CYRILLIC SMALL LETTER BE
 ;;; % CYRILLIC CAPITAL LETTER BE
 ;;; % CYRILLIC SMALL LETTER VE
 ;;; % CYRILLIC CAPITAL LETTER VE
...
order_end

Now we can return to sorting the examples from the beginning of the article. The catch lies in this part of the weight table:

IGNORE;IGNORE;IGNORE; % SPACE
 IGNORE;IGNORE;IGNORE; % EXCLAMATION MARK
 IGNORE;IGNORE;IGNORE; % QUOTATION MARK
...

It is clear that in this table, punctuation marks from the table ASCII (including spaces) are almost always ignored when comparing strings. The only exceptions are strings that match in every way except for punctuation marks that occur in matching positions. The strings from my example (after sorting) look like this for the comparison algorithm:

AbakanovMikhailPainter
YolkinaEllacrane
IvanovaAllaPainter
IvanovAndreiJoiner

Considering that in the weight table, uppercase letters in the Russian language come after lowercase letters (at the third level <CAP> heavier than <MIN>), the sorting appears absolutely correct.

When setting the variable LC_COLLATE=C a special table is loaded that defines byte-by-byte comparison

static const uint32_t collseqwc[] =
{
  8, 1, 8, 0x0, 0xff,
  \/ * 1st-level table *\/ 
  6 * sizeof (uint32_t),
  \/ * 2nd-level table *\/ 
  7 * sizeof (uint32_t),
  \/ * 3rd-level table *\/ 
  L'x00', L'x01', L'x02', L'x03', L'x04', L'x05', L'x06', L'x07',
  L'x08', L'x09', L'x0a', L'x0b', L'x0c', L'x0d', L'x0e', L'x0f',

...
  L'xf8', L'xf9', L'xfa', L'xfb', L'xfc', L'xfd', L'fe', L'xff'
};

Since in Unicode the code point for Ё is before A, the strings are sorted accordingly.

Text and binary tables

It is obvious that string comparison is an extremely common operation, while parsing the table CTT is a rather expensive procedure. To optimize access to the table, it is compiled into binary form by the command localedef.

The command localedef takes as parameters a file with the table of national features (option -i), in which all characters are represented by Unicode points, and a file of correspondence between Unicode points and characters of a specific encoding (option -f). As a result of its execution, binary files for the locale are created, with a name specified in the last parameter.

Glibc supports two formats of binary files: "traditional" and "modern".

The traditional format implies that the locale name is the name of the subdirectory in /usr/lib/locale/. This subdirectory stores binary files LC_COLLATE, LC_CTYPE, LC_TIME and so on. The file LC_IDENTIFICATION contains the formal name of the locale (which may differ from the directory name) and comments.

The modern format assumes storing all locales in a single archive /usr/lib/locale/locale-archive, which is mapped into the virtual memory of all processes using it. glibcThe locale name in the modern format undergoes some canonization—only letters and digits are retained in the encoding names, converted to lowercase. Thus ru_RU.KOI8-R, will be preserved as ru_RU.koi8r.

Input files are searched in the current directory, as well as in the directories /usr/share/i18n/locales/ and /usr/share/i18n/charmaps/ for files CTT and encoding files respectively.

For example, the command

localedef -i ru_RU -f MAC-CYRILLIC ru_RU.MAC-CYRILLIC

will compile the file /usr/share/i18n/locales/ru_RU using the encoding file /usr/share/i18n/charmaps/MAC-CYRILLIC.gz and save the result as /usr/lib/locale/locale-archive under the name ru_RU.maccyrillic

If the variable LANG=en_US.UTF-8 is set, then glibc it will look for binary locale files in the following sequence of files and directories:

/usr/lib/locale/locale-archive
/usr/lib/locale/en_US.UTF-8/
/usr/lib/locale/en_US/
/usr/lib/locale/enUTF-8/
/usr/lib/locale/en/

If the locale is found in both traditional and modern formats, priority is given to the modern one.

You can view the list of compiled locales with the command locale -a.

Preparing your own collation table

Now, armed with knowledge, you can create your own perfect string collation table. This table should correctly compare Russian letters, including the letter Ё, while considering punctuation marks according to the table ASCII.

The process of preparing your sorting table consists of two stages: editing the weight table and compiling it into binary form with the command localedef.

To adjust the comparison table with minimal editing effort, the format open-std.org provides for sections that adjust the weights of the existing table. The section starts with the keyword reorder-after and an indication of the position after which the replacement occurs. The section ends with the line reorder-end.If it's necessary to correct several areas of the table, a section is created for each of these areas.

I copied the new versions of the files iso14651_t1_common and ru_RU from the repository glibc to my home directory ~/ .local / share / i18n / locales / and slightly edited the section LC_COLLATE downward API support (simultaneously with this in ru_RU. The new versions of the files are fully compatible with my version glibc. If you want to use the old versions of the files, you will have to change the symbolic names and the location from which the replacement starts in the table.

LC_COLLATE
% Copy the template from ISO/IEC 14651
copy "iso14651_t1"
reorder-after 
 ;;; % SPACE
 ;;; % EXCLAMATION MARK
 ;;; % QUOTATION MARK
...
 ;;; % RIGHT CURLY BRACKET
 ;;; % TILDE
reorder-end
END LC_COLLATE

In fact, the fields would need to be changed in LC_IDENTIFICATION so that they point to the locale ru_MY, but in my example this was not needed as I excluded locales from the archive search locale-archive.

To localedef worked with files in my folder through the variable I18NPATH you can add an additional directory for input file search, and the directory for saving binary files can be specified as a path with slashes:

$> I18NPATH=~/.local/share/i18n localedef -i ru_RU -f UTF-8 ~/.local/lib/locale/ru_MY.UTF-8

POSIX assumes that in LANG you can write absolute paths to directories with locale files starting with a forward slash, but glibc downward API support (simultaneously with this in Linux all paths are counted from the base directory, which can be overridden by the variable LOCPATH. After setting LOCPATH=~/.local/lib/locale/ all files related to localization will only be searched in my folder. The locale archive when the variable is set LOCPATH is ignored.

Here’s the decisive test:

$> LANG=ru_MY.UTF-8 LOCPATH=~/.local/lib/locale/ sort buhg.txt
Abakanov Mikhail;painter
Yolkina Ella;crane operator
Ivanov Andrey;plumber
Ivanova Alla;lawyer

Hooray! We did it!

Learning from Mistakes

I already answered the questions about string sorting posed at the beginning, but there are still a couple of questions about errors — visible and invisible.

Let's go back to the original task.

And the program sort and the program join use the same string comparison functions from glibc. How did it happen that join gave a sorting error on the lines sorted by the command sort in the locale en_US.UTF-8? Ответ прост: sort compares the entire string, while join only compares the key, which by default is the beginning of the string up to the first whitespace character. In my example, this led to an error message because the sorting of the first words in the lines did not match the sorting of the full strings.

The locale "C" ensures that in the sorted strings, the initial substrings up to the first space are also sorted, but this just masks the error. You can create such data (people with the same last names but different first names) that without an error message would yield incorrect results in file merging. If we want that join When merging file lines by full name, the correct approach is to explicitly specify the field separator and sort by the key field, not by the entire line. In this case, both the merge will proceed correctly, and there will be no errors in any locale:

$> sort -t ; -k 1 buhg.txt > buhg.srt
$> sort -t ; -k 1 mail.txt > mail.srt
$> join -t ; buhg.srt mail.srt > result

Successfully completed example in encoding CP1251 contains another error. The thing is, in all the distributions I know of Linux the packages lack a compiled locale ru_RU.CP1251. If a compiled locale is not found, then sort it silently uses byte-by-byte comparison, which is what we observed.

By the way, there is another small glitch related to the unavailability of compiled locales. The command LOCPATH=/tmp locale -a will list all locales in locale-archive, but with the variable set LOCPATH for all programs (including the locale) those locales will be unavailable.

$> LOCPATH=/tmp locale -a | grep en_US
locale: Cannot set LC_CTYPE to default locale: No such file or directory
locale: Cannot set LC_MESSAGES to default locale: No such file or directory
locale: Cannot set LC_COLLATE to default locale: No such file or directory
en_US
en_US.iso88591
en_US.iso885915
en_US.utf8

$> LC_COLLATE=en_US.UTF-8 sort --debug
sort: using ‘en_US.UTF-8’ sorting rules

$> LOCPATH=/tmp LC_COLLATE=en_US.UTF-8 sort --debug
sort: using simple byte comparison

Conclusion

If you are a programmer who tends to think of strings as a collection of bytes, then your choice LC_COLLATE=C.

If you are a linguist or a dictionary compiler, it is better for you to compile your locale.

If you are a regular user, you just need to get used to the fact that the command ls -a outputs files that start with a dot, mixed with files that start with a letter, and Midnight Commander, which uses its internal functions to sort names, brings files starting with a dot to the beginning of the list.