Axel Beckert wrote:

Cloning of https://bugs.debian.org/781657 failed due to merged bugs.
So I rather just open a new one. My mail already had all relevant
information:
[Dropping the non-relevant stuff which only applied to needrestart]

		Regards, Axel

The issue actually does not just occur as the beginning of a string.
What matters is where the first group of non-word characters occurs;
this is an additional bug, because there's no reason to apply a rule
on the first group of non-word characters but not the other ones.
As I've said in the upstream bug, the author forgot the g flag.
But anyway, the removal of the non-word characters is done too
early, in particular, before numbers are recognized.

I've done two suggestions in the upstream bug
https://github.com/bingos/sort-naturally/issues/3 to fix this bug.

Note that https://github.com/bingos/sort-naturally/issues/1 seems
to actually be the same bug.