There's Unicode Collation Algorithm that can translate any Unicode string into a trivially-comparable binary string. You can map string -> collation string, and

There's Unicode Collation Algorithm that can translate any Unicode string into a trivially-comparable binary string. You can map string -> collation string, and sort on that. It's not very expensive to compute, and you can store it explicitly as a separate column if you need to. The only pain is that the collation algorithm is locale-dependent. It's not possible to have one universal mapping, because there are languages that have conflicting rules regarding the same characters (e.g. Swedish and German handling of umlauts), so if you're going to materialize/index the collation string, you'll have to choose who to disappoint.