Abgesehen von der perllocale-Lösung (Cheatah):
Im sort() kannst Du eine *eigene* Vergleicher-Funktion verwenden.
Diese könnte die beiden Strings nehmen, *lokal* die Ersetzen von ä nach ae vornehmen, *dann* vergleichen und das Ergebnis zurückliefern.
Dann wäre nichts rückgängig zu machen.