The 'Natural Sort Order' algorithm

This algorithm (short NSO) is used to sort strings with numbers and characters in a natural way.


this should be an image

Sorry, but it can't sort chips...

Some operating systems like Windows (since XP) have that exact algorithm implemented inside the explorer to sort files inside a directory. A quick example:

  • Without NSO: 03.png, 0t.png, 1.png, 10.png, 11.png, 2.png, p.png, t1.png, t10.png, t2.png
  • With NSO: 0t.png, 1.png, 2.png, 03.png, 10.png, 11.png, p.png, t1.png, t2.png, t10.png

In Windows, this functionality can be found in a specific system DLL that contains the API function StrCmpLogicalW or you can simply implement the algorithm yourself using regex.

This algorithm also works for folder names or names (strings) in general. You should only be careful with paths, because if the paths contain numbers and the program logic is not prepared for this, the numerical values in the paths will disrupt the sequence.

Beware that, if you are working with files, you only have to work with the filennames without the file extensions!

Solving the problem without an algorithm

You can simply write the numbers inside the strings with leading zeros, like this:
00t.png, 01.png, 02.png, 03.png, 10.png, 11.png, p.png, t01.png, t02.png, t10.png

Once you have higher values (100s, 1000s ...) you simply fill the digits with zeros until you have the given length of the highest number:

  • 100s: 001.png, 002.png, 003.png ... 010.png, 011.png, ... 100.png, 101.png ... 999.png
  • 100s: 0001.png, 0002.png, 0003.png ... 0010.png, 0011.png, ... 0100.png, 0101.png ... 1000.png, 1001.png ... 9999.png
  • etc.

The algorithm (steps)

  1. Find out, what the largest number inside the list of strings is (in the example from above it is 11). To do this, look at each file name and use the regex \d+ (find the first combination of numbers with x digits in the current file name, i.e. 03, 0, 1, 10 ...).
  2. Find the length of the largest number or in other words the number of digits (in the example from above it is 2)
  3. Fill all numerical values in the list of strings with zeros using a string function until the length of the maximum number has been reached (without changing the actual file names themselves). The example would look like this: 03.png, 00t.png, 01.png, 10.png, 11.png, 02.png, p.png, t01.png, t10.png, t02.png. It is important here that the number strings (0, 1, 2 etc.) are considered, without the letters. For example, if you try to make the string 0t 2 digits long, nothing will happen because it is already 2 chars long. However, the string 0 can be extended to 00. This results in the file name 00t instead of 0t, so that, for example "00t" < "03" = True" applies, whereas "0t" < "03" = False applies.
  4. Re-sort the list of strings using a list sort function. This works because, for example, string 02 is smaller than string 11. For example, "02" < "11" = True and "2" < "11" = False apply, which incidentally is part of the core problem that NSO solves.