Еже ли локаль все-таки существует в БД локалей, но просто не установлена - то POSIX::setlocale.
Еже ли нет даже упоминания о ней - создаете хеш, типа
$h{номер буквы(ord)}=\'порядок буквы\' (задаете порядок на множестве букв руками) и вперед по хеш таблице сортировать.