Zoals je hebt opgemerkt, vertrouwt Postgres op het besturingssysteem om te sorteren, en Postgres kan weinig doen aan de manier waarop dingen worden verzameld, behalve rechtstreeks aansluiten op de ICU.
Dit is door de jaren heen een terugkerend discussieonderwerp geweest, maar het is geen triviale taak:
http://wiki.postgresql.org/wiki/Todo:ICU