[ ![avatar](/assets/img/avatar.png) ](/)

[ Miigon's blog ](/)

My ideas, thoughts and experiences

  * [ __ HOME  ](/)
  * [ __ CATEGORIES  ](/categories/)
  * [ __ TAGS  ](/tags/)
  * [ __ ARCHIVES  ](/archives/)
  * [ __ ABOUT  ](/about/)

__ [ __ ](https://github.com/Miigon) [ __ ](https://twitter.com/) [ __
](javascript:location.href = 'mailto:' +
\['miigon.pg','gmail.com'\].join\('@'\)) [ __ ](/feed.xml)

[ Home ](/) Natural Sort: How to sort file names naturally  __

Post

__ __ Cancel

#  Natural Sort: How to sort file names naturally

Posted _Apr 13, 2021_

By _[ Miigon ](https://github.com/Miigon) _

_3 min_ read

#  What’s the problem?

When a programmer is given the task of sorting file names in a list, it might
be tempting to sort using something like ` std::sort() ` . The problem with
that is: ` std::sort() ` sorts alphabetically. Suppose we have a list of file
like this:

__ __

`

    
    
    1
    2
    3
    4
    5
    6
    7
    8
    

|

    
    
    chapter1.txt
    chapter10.txt
    chapter2.txt
    chapter3p1.txt
    chapter3p2.txt
    chapter3p10.txt
    chapter11.txt
    chapter20.txt
      
  
---|---  
`

If we sort it alphabetically, aka, using ` std::sort() ` (or `
Array.prototype.sort() ` for JavaScript), what would happen?

__ __

`

    
    
    1
    2
    3
    4
    5
    6
    7
    8
    

|

    
    
    chapter1.txt
    chapter10.txt
    chapter11.txt
    chapter2.txt       # we expect chapter 2 to be in front of chapter10
    chapter20.txt
    chapter3p1.txt
    chapter3p10.txt
    chapter3p2.txt
      
  
---|---  
`

We see that ` chapter10 ` and ` chapter11 ` have been placed before ` chapter2
` . This make sense for an alphabetically sorted list. Both ` 10 ` and ` 11 `
is smaller than ` 2 ` since the first digit ` 1 ` is smaller than ` 2 ` .
However, it does not follow our intuition. As a human, we expect ` 2 ` to be
bigger than ` 10 ` , not the other way around.

#  Natural sort

This is where the algorithm of [ natural sort
](https://en.wikipedia.org/wiki/Natural_sort_order) (sometimes called
alphanumerical sort) comes in handy.

> Natural sort order is an ordering of strings in alphabetical order, except
> that multi-digit numbers are treated atomically, i.e., as if they were a
> single character. Natural sort order has been promoted as being more human-
> friendly (“natural”) than the machine-oriented pure alphabetical order.

Pseudo-code for natural sort:

__ __

`

    
    
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    

|

    
    
    # Preprocessing
    For every file name in list:
        processedName = []
        Scan for every character c in file name:
            If consecutive digits are found:
                Merge consecutive numerical characters into a single number
                processedName.Append(number)
            Else:
                # non-numerical character
                processedName.Append(c)
        list[current] = processedName  # use the new name as name for comparison
    
    Sort list:
        Comparing file name x and y:
            For every cooresponding [xi in x] and [yi in y]:
                If xi == yi:
                    Continue
                If both xi and yi are numbers:
                    If xi < yi: x is smaller
                    Else: y is smaller
                Else If both xi and yi are strings:
                    If xi < yi: x is smaller
                    Else: y is smaller
                Else: # One of xi or yi is a number and the other is string
                    If xi is number: x is smaller
                    Else: y is smaller
    
    # the list is now sorted naturally (or alphanumerically)!
      
  
---|---  
`

After applying the algorithm, the list should look like this:

__ __

`

    
    
    1
    2
    3
    4
    5
    6
    7
    8
    

|