Setting LC_ALL=C gives the Unicode sequence for Perl's sort but
Sort::Naturally still does not seem correct:
LC_ALL=C ./sort-test.pl
unsorted : 4 A X i 1 x 10 a B ä y z į C Ä b c Į Y Z än and
ÄND And Any ant Äm Äs
no locale, perl : 1 10 4 A And Any B C X Y Z a and ant b c i x y z
Ä ÄND Äm Äs ä än Į į
no locale, naturally : 1 4 10 Ä ä A a And and ant Any B b C c i Äm än
ÄND Äs X x Y y Z z Į į
use locale, perl : 1 10 4 A And Any B C X Y Z a and ant b c i x y z
Ä ÄND Äm Äs ä än Į į
use locale, naturally : 1 4 10 Ä ä A a And and ant Any B b C c i Äm än
ÄND Äs X x Y y Z z Į į
use locale, perl num : 1 4 10 A And Any B C X Y Z a and ant b c i x y z
Ä ÄND Äm Äs ä än Į į