Version sort ordering
*********************

Version sort overview
=====================

Version sort puts items such as file names and lines of text in an order that feels natural to people, when the text contains a mixture of letters and digits.

Lexicographic sorting usually does not produce the order that one expects because comparisons are made on a character-by-character basis.

Compare the sorting of the following items:

     Lexicographic sort:          Version Sort:

     a1                           a1
     a120                         a2
     a13                          a13
     a2                           a120

Version sort functionality in GNU Coreutils is available in the ls -v, ls --sort=version, sort -V, and sort --version-sort commands.

Using version sort in GNU Coreutils
-----------------------------------

Two GNU Coreutils programs use version sort: ls and sort.

To list files in version sort order, use ls with the -v or --sort=version option:

     default sort:              version sort:

     $ ls -1                    $ ls -1 -v
     a1                         a1
     a100                       a1.4
     a1.13                      a1.13
     a1.4                       a1.40
     a1.40                      a2
     a2                         a100

To sort text files in version sort order, use sort with the -V or --version-sort option:

     $ cat input
     b3
     b11
     b1
     b20

     lexicographic order:       version sort order:

     $ sort input               $ sort -V input
     b1                         b1
     b11                        b3
     b20                        b11
     b3                         b20

To sort a specific field in a file, use -k/--key with V type sorting, which is often combined with b to ignore leading blanks in the field:

     $ cat input2
     100   b3   apples
     2000  b11  oranges
     3000  b1   potatoes
     4000  b20  bananas
     $ sort -k 2bV,2 input2
     3000  b1   potatoes
     100   b3   apples
     2000  b11  oranges
     4000  b20  bananas

Version sort and natural sort
-----------------------------

In GNU Coreutils, the name version sort was chosen because it is based on Debian GNU/Linux's algorithm of sorting packages' versions.

Its goal is to answer questions like ``Which package is newer, firefox-60.7.2 or firefox-60.12.3?''

In Coreutils this algorithm was slightly modified to work on more general input such as textual strings and file names (see Differences from Debian version sort).

In other contexts, such as other programs and other programming languages, a similar sorting functionality is called natural sort (https://en.wikipedia.org/wiki/Natural_sort_order).

Variations in version sort order
--------------------------------

Currently there is no standard for version sort.

That is: there is no one correct way or universally agreed-upon way to order items. Each program and each programming language can decide its own ordering algorithm and call it ``version sort'', ``natural sort'', or other names.

See Other version/natural sort implementations for many examples of differing sorting possibilities, each with its own rules and variations.

If you find a bug in the Coreutils implementation of version-sort, please report it.  See Reporting version sort bugs.

Version sort implementation
===========================

GNU Coreutils version sort is based on the ``upstream version'' part of Debian's versioning scheme (https://www.debian.org/doc/debian-policy/ch-controlfields.html#version).

This section describes the GNU Coreutils sort ordering rules.

The next section (Differences from Debian version sort) describes some differences between GNU Coreutils and Debian version sort.

Version-sort ordering rules
---------------------------

The version sort ordering rules are:

 1. The strings are compared from left to right.

 2. First the initial part of each string consisting entirely of non-digit bytes is determined.

      A. These two parts (either of which may be empty) are compared lexically. If a difference is found it is returned.

      B. The lexical comparison is a lexicographic comparison of byte strings, except that:

           a. ASCII letters sort before other bytes.

           b. A tilde sorts before anything, even an empty string.

 3. Then the initial part of the remainder of each string that contains all the leading digits is determined. The numerical values represented by these two parts are compared, and any difference found is returned as the result of the comparison.

      A. For these purposes an empty string (which can only occur at the end of one or both version strings being compared) counts as zero.

      B. Because the numerical value is used, non-identical strings can compare equal.  For example, 123 compares equal to 00123, and the empty string compares equal to 0.

 4. These two steps (comparing and removing initial non-digit strings and initial digit strings) are repeated until a difference is found or both strings are exhausted.

Consider the version-sort comparison of two file names: foo07.7z and foo7a.7z. The two strings will be broken down to the following parts, and the parts compared respectively from each string:

     foo  vs  foo   (rule 2, non-digits)
     07   vs  7     (rule 3, digits)
     .    vs  a.    (rule 2)
     7    vs  7     (rule 3)
     z    vs  z     (rule 2)

Comparison flow based on above algorithm:

 1. The first parts (foo) are identical.

 2. The second parts (07 and 7) are compared numerically, and compare equal.

 3. The third parts (. vs a.) are compared lexically by ASCII value (rule 2.B).

 4. The first byte of the first string (.) is compared to the first byte of the second string (a).

 5. Rule 2.B.a says letters sorts before non-letters. Hence, a comes before ..

 6. The returned result is that foo7a.7z comes before foo07.7z.

Result when using sort:

     $ cat input3
     foo07.7z
     foo7a.7z
     $ sort -V input3
     foo7a.7z
     foo07.7z

See Differences from Debian version sort for additional rules that extend the Debian algorithm in Coreutils.

Version sort is not the same as numeric sort
--------------------------------------------

Consider the following text file:

     $ cat input4
     8.10
     8.5
     8.1
     8.01
     8.010
     8.100
     8.49

     Numerical Sort:                   Version Sort:

     $ sort -n input4                  $ sort -V input4
     8.01                              8.01
     8.010                             8.1
     8.1                               8.5
     8.10                              8.010
     8.100                             8.10
     8.49                              8.49
     8.5                               8.100

Numeric sort (sort -n) treats the entire string as a single numeric value, and compares it to other values. For example, 8.1, 8.10 and 8.100 are numerically equivalent, and are ordered together. Similarly, 8.49 is numerically less than 8.5, and appears before first.

Version sort (sort -V) first breaks down the string into digit and non-digit parts, and only then compares each part (see annotated example in Version-sort ordering rules).

Comparing the string 8.1 to 8.01, first the 8s are compared (and are identical), then the dots (.) are compared and are identical, and lastly the remaining digits are compared numerically (1 and 01) -- which are numerically equal.  Hence, 8.01 and 8.1 are grouped together.

Similarly, comparing 8.5 to 8.49 -- the 8 and . parts are identical, then the numeric values 5 and 49 are compared. The resulting 5 appears before 49.

This sorting order (where 8.5 comes before 8.49) is common when assigning versions to computer programs (while perhaps not intuitive or ``natural'' for people).

Version sort punctuation
------------------------

Punctuation is sorted by ASCII order (rule 2.B).

     $ touch 1.0.5_src.tar.gz 1.0_src.tar.gz
     $ ls -v -1
     1.0.5_src.tar.gz
     1.0_src.tar.gz

Why is 1.0.5_src.tar.gz listed before 1.0_src.tar.gz?

Based on the version-sort ordering rules, the strings are broken down into the following parts:

               1   vs  1               (rule 3, all digits)
               .   vs  .               (rule 2, all non-digits)
               0   vs  0               (rule 3)
               .   vs  _src.tar.gz     (rule 2)
               5   vs  empty string    (no more bytes in the file name)
     _src.tar.gz   vs  empty string

The fourth parts (. and _src.tar.gz) are compared lexically by ASCII order. The . (ASCII value 46) is less than _ (ASCII value 95) -- and should be listed before it.

Hence, 1.0.5_src.tar.gz is listed first.

If a different byte appears instead of the underscore (for example, percent sign % ASCII value 37, which is less than dot's ASCII value of 46), that file will be listed first:

     $ touch   1.0.5_src.tar.gz     1.0%zzzzz.gz
     1.0%zzzzz.gz
     1.0.5_src.tar.gz

The same reasoning applies to the following example, as . with ASCII value 46 is less than / with ASCII value 47:

     $ cat input5
     3.0/
     3.0.5
     $ sort -V input5
     3.0.5
     3.0/

Punctuation vs letters
----------------------

Rule 2.B.a says letters sort before non-letters (after breaking down a string to digit and non-digit parts).

     $ cat input6
     a%
     az
     $ sort -V input6
     az
     a%

The input strings consist entirely of non-digits, and based on the above algorithm have only one part, all non-digits (a% vs az).

Each part is then compared lexically, byte-by-byte; a compares identically in both strings.

Rule 2.B.a says a letter like z sorts before a non-letter like % -- hence az appears first (despite z having ASCII value of 122, much larger than % with ASCII value 37).

The tilde ~
-----------

Rule 2.B.b says the tilde ~ (ASCII 126) sorts before other bytes, and before an empty string.

     $ cat input7
     1
     1%
     1.2
     1~
     ~
     $ sort -V input7
     ~
     1~
     1
     1%
     1.2

The sorting algorithm starts by breaking down the string into non-digit (rule 2) and digit parts (rule 3).

In the above input file, only the last line in the input file starts with a non-digit (~). This is the first part. All other lines in the input file start with a digit -- their first non-digit part is empty.

Based on rule 2.B.b, tilde ~ sorts before other bytes and before the empty string -- hence it comes before all other strings, and is listed first in the sorted output.

The remaining lines (1, 1%, 1.2, 1~) follow similar logic: The digit part is extracted (1 for all strings) and compares equal. The following extracted parts for the remaining input lines are: empty part, %, ., ~.

Tilde sorts before all others, hence the line 1~ appears next.

The remaining lines (1, 1%, 1.2) are sorted based on previously explained rules.

Version sort ignores locale
---------------------------

In version sort, Unicode characters are compared byte-by-byte according to their binary representation, ignoring their Unicode value or the current locale.

Most commonly, Unicode characters are encoded as UTF-8 bytes; for example, GREEK SMALL LETTER ALPHA (U+03B1, α) is encoded as the UTF-8 sequence 0xCE 0xB1).  The encoding is compared byte-by-byte, e.g., first 0xCE (decimal value 206) then 0xB1 (decimal value 177).

     $ touch aa az "a%" "aα"
     $ ls -1 -v
     aa
     az
     a%
     aα

Ignoring the first letter (a) which is identical in all strings, the compared values are:

a and z are letters, and sort before all other non-digits.

Then, percent sign % (ASCII value 37) is compared to the first byte of the UTF-8 sequence of α, which is 0xCE or 206). The value 37 is smaller, hence a% is listed before aα.

Differences from Debian version sort
====================================

GNU Coreutils version sort differs slightly from the official Debian algorithm, in order to accommodate more general usage and file name listing.

Hyphen-minus - and colon :
--------------------------

In Debian's version string syntax the version consists of three parts:

     [epoch:]upstream_version[-debian_revision]

The epoch and debian_revision parts are optional.

Example of such version strings:

     60.7.2esr-1~deb9u1
     52.9.0esr-1~deb9u1
     1:2.3.4-1+b2
     327-2
     1:1.0.13-3
     2:1.19.2-1+deb9u5

If the debian_revision part is not present, hyphens - are not allowed. If epoch is not present, colons : are not allowed.

If these parts are present, hyphen and/or colons can appear only once in valid Debian version strings.

In GNU Coreutils, such restrictions are not reasonable (a file name can have many hyphens, a line of text can have many colons).

As a result, in GNU Coreutils hyphens and colons are treated exactly like all other punctuation, i.e., they are sorted after letters.  See Version sort punctuation.

In Debian, these characters are treated differently than in Coreutils: a version string with hyphen will sort before similar strings without hyphens.

Compare:

     $ touch 1ab-cd 1abb
     $ ls -v -1
     1abb
     1ab-cd
     $ if dpkg --compare-versions 1abb lt 1ab-cd
     > then echo sorted
     > else echo out of order
     > fi
     out of order

For further details, see Comparing two strings using Debian's algorithm and GNU Bug 35939 (https://bugs.gnu.org/35939).

Special priority in GNU Coreutils version sort
----------------------------------------------

In GNU Coreutils version sort, the following items have special priority and sort before all other strings (listed in order):

 1. The empty string

 2. The string . (a single dot, ASCII 46)

 3. The string .. (two dots)

 4. Strings starting with dot (.) sort before strings starting with any other byte.

Example:

     $ printf '%s\n' a "" b "." c  ".."  ".d20" ".d3"  | sort -V
     .
     ..
     .d3
     .d20
     a
     b
     c

These priorities make perfect sense for ls -v: The special files dot . and dot-dot .. will be listed first, followed by any hidden files (files starting with a dot), followed by non-hidden files.

For sort -V these priorities might seem arbitrary. However, because the sorting code is shared between the ls and sort program, the ordering rules are the same.

Special handling of file extensions
-----------------------------------

GNU Coreutils version sort implements specialized handling of strings that look like file names with extensions. This enables slightly more natural ordering of file names.

The following additional rules apply when comparing two strings where both begin with non-..  They also apply when comparing two strings where both begin with . but neither is . or ...

 1. A suffix (i.e., a file extension) is defined as: a dot, followed by an ASCII letter or tilde, followed by zero or more ASCII letters, digits, or tildes; all repeated zero or more times, and ending at string end. This is equivalent to matching the extended regular expression (\.[A-Za-z~][A-Za-z0-9~]*)*$ in the C locale. The longest such match is used, except that a suffix is not allowed to match an entire nonempty string.

 2. The suffixes are temporarily removed, and the strings are compared without them, using version sort (see Version-sort ordering rules) without special priority (see Special priority in GNU Coreutils version sort).

 3. If the suffix-less strings do not compare equal, this comparison result is used and the suffixes are effectively ignored.

 4. If the suffix-less strings compare equal, the suffixes are restored and the entire strings are compared using version sort.

Examples for rule 1:

  * hello-8.txt: the suffix is .txt

  * hello-8.2.txt: the suffix is .txt (.2 is not included because the dot is not followed by a letter)

  * hello-8.0.12.tar.gz: the suffix is .tar.gz (.0.12 is not included)

  * hello-8.2: no suffix (suffix is an empty string)

  * hello.foobar65: the suffix is .foobar65

  * gcc-c++-10.8.12-0.7rc2.fc9.tar.bz2: the suffix is .fc9.tar.bz2 (.7rc2 is not included as it begins with a digit)

  * .autom4te.cfg: the suffix is the entire string.

Examples for rule 2:

  * Comparing hello-8.txt to hello-8.2.12.txt, the .txt suffix is temporarily removed from both strings.

  * Comparing foo-10.3.tar.gz to foo-10.tar.xz, the suffixes .tar.gz and .tar.xz are temporarily removed from the strings.

Example for rule 3:

  * Comparing hello.foobar65 to hello.foobar4, the suffixes (.foobar65 and .foobar4) are temporarily removed. The remaining strings are identical (hello). The suffixes are then restored, and the entire strings are compared (hello.foobar4 comes first).

Examples for rule 4:

  * When comparing the strings hello-8.2.txt and hello-8.10.txt, the suffixes (.txt) are temporarily removed. The remaining strings (hello-8.2 and hello-8.10) are compared as previously described (hello-8.2 comes first). (In this case the suffix removal algorithm does not have a noticeable effect on the resulting order.)

How does the suffix-removal algorithm effect ordering results?

Consider the comparison of hello-8.txt and hello-8.2.txt.

Without the suffix-removal algorithm, the strings will be broken down to the following parts:

     hello-  vs  hello-  (rule 2, all non-digits)
     8       vs  8       (rule 3, all digits)
     .txt    vs  .       (rule 2)
     empty   vs  2
     empty   vs  .txt

The comparison of the third parts (. vs .txt) will determine that the shorter string comes first -- resulting in hello-8.2.txt appearing first.

Indeed this is the order in which Debian's dpkg compares the strings.

A more natural result is that hello-8.txt should come before hello-8.2.txt, and this is where the suffix-removal comes into play:

The suffixes (.txt) are removed, and the remaining strings are broken down into the following parts:

     hello-  vs  hello-  (rule 2, all non-digits)
     8       vs  8       (rule 3, all digits)
     empty   vs  .       (rule 2)
     empty   vs  2

As empty strings sort before non-empty strings, the result is hello-8 being first.

A real-world example would be listing files such as: gcc_10.fc9.tar.gz and gcc_10.8.12.7rc2.fc9.tar.bz2: Debian's algorithm would list gcc_10.8.12.7rc2.fc9.tar.bz2 first, while ls -v will list gcc_10.fc9.tar.gz first.

These priorities make sense for ls -v: Versioned files will be listed in a more natural order.

For sort -V these priorities might seem arbitrary. However, because the sorting code is shared between the ls and sort program, the ordering rules are the same.

Comparing two strings using Debian's algorithm
----------------------------------------------

The Debian program dpkg (available on all Debian and Ubuntu installations) can compare two strings using the --compare-versions option.

To use it, create a helper shell function (simply copy & paste the following snippet to your shell command-prompt):

     compver() {
       if dpkg --compare-versions "$1" lt "$2"
       then printf '%s\n' "$1" "$2"
       else printf '%s\n' "$2" "$1"
       fi
     }

Then compare two strings by calling compver:

     $ compver 8.49 8.5
     8.5
     8.49

Note that dpkg will warn if the strings have invalid syntax:

     $ compver "foo07.7z" "foo7a.7z"
     dpkg: warning: version 'foo07.7z' has bad syntax:
                    version number does not start with digit
     dpkg: warning: version 'foo7a.7z' has bad syntax:
                    version number does not start with digit
     foo7a.7z
     foo07.7z
     $ compver "3.0/" "3.0.5"
     dpkg: warning: version '3.0/' has bad syntax:
                    invalid character in version number
     3.0.5
     3.0/

To illustrate the different handling of hyphens between Debian and Coreutils algorithms (see Hyphen-minus and colon):

     $ compver abb ab-cd 2>/dev/null     $ printf 'abb\nab-cd\n' | sort -V
     ab-cd                               abb
     abb                                 ab-cd

To illustrate the different handling of file extension: (see Special handling of file extensions):

     $ compver hello-8.txt hello-8.2.txt 2>/dev/null
     hello-8.2.txt
     hello-8.txt
     $ printf '%s\n' hello-8.txt hello-8.2.txt | sort -V
     hello-8.txt
     hello-8.2.txt

Advanced Topics
===============

Reporting version sort bugs
---------------------------

If you suspect a bug in GNU Coreutils version sort (i.e., in the output of ls -v or sort -V), please first check the following:

 1. Is the result consistent with Debian's own ordering (using dpkg, see Comparing two strings using Debian's algorithm)? If it is, then this is not a bug -- please do not report it.

 2. If the result differs from Debian's, is it explained by one of the sections in Differences from Debian version sort? If it is, then this is not a bug -- please do not report it.

 3. If you have a question about specific ordering which is not explained here, please write to coreutils@gnu.org, and provide a concise example that will help us diagnose the issue.

 4. If you still suspect a bug which is not explained by the above, please write to bug-coreutils@gnu.org with a concrete example of the suspected incorrect output, with details on why you think it is incorrect.

Other version/natural sort implementations
------------------------------------------

As previously mentioned, there are multiple variations on version/natural sort, each with its own rules. Some examples are:

  * Natural Sorting variants in Rosetta Code (https://rosettacode.org/wiki/Natural_sorting).

  * Python's natsort package (https://pypi.org/project/natsort/) (includes detailed description of their sorting rules: natsort -- how it works (https://natsort.readthedocs.io/en/master/howitworks.html)).

  * Ruby's version_sorter (https://github.com/github/version_sorter).

  * Perl has multiple packages for natural and version sorts (each likely with its own rules and nuances): Sort::Naturally (https://metacpan.org/pod/Sort::Naturally), Sort::Versions (https://metacpan.org/pod/Sort::Versions), CPAN::Version (https://metacpan.org/pod/CPAN::Version).

  * PHP has a built-in function natsort (https://www.php.net/manual/en/function.natsort.php).

  * NodeJS's natural-sort package (https://www.npmjs.com/package/natural-sort).

  * In zsh, the glob modifier (http://zsh.sourceforge.net/Doc/Release/Expansion.html#Glob-Qualifiers) *(n) will expand to files in natural sort order.

  * When writing C programs, the GNU libc library (glibc) provides the strverscmp(3) (https://man7.org/linux/man-pages/man3/strverscmp.3.html) function to compare two strings, and versionsort(3) (https://man7.org/linux/man-pages/man3/versionsort.3.html) function to compare two directory entries (despite the names, they are not identical to GNU Coreutils version sort ordering).

  * Using Debian's sorting algorithm in:

       * python: Stack Overflow Example #4957741 (https://stackoverflow.com/a/4957741).

       * NodeJS: deb-version-compare (https://www.npmjs.com/package/deb-version-compare).

Related source code
-------------------

  * Debian's code which splits a version string into epoch/upstream_version/debian_revision parts: parsehelp.c:parseversion() (https://git.dpkg.org/cgit/dpkg/dpkg.git/tree/lib/dpkg/parsehelp.c#n191).

  * Debian's code which performs the upstream_version comparison: version.c (https://git.dpkg.org/cgit/dpkg/dpkg.git/tree/lib/dpkg/version.c#n140).

  * Gnulib code (used by GNU Coreutils) which performs the version comparison: filevercmp.c (https://git.savannah.gnu.org/cgit/gnulib.git/tree/lib/filevercmp.c).