Som du har bemærket, er Postgres afhængig af operativsystemet til at levere sortering, og der er meget lidt Postgres kan gøre ved, hvordan tingene bliver sorteret ud over at tilslutte sig direkte til ICU.
At gøre det har været et tilbagevendende diskussionsemne gennem årene, men det er ikke en triviel opgave:
http://wiki.postgresql.org/wiki/Todo:ICU