Its worse than that. None of this weirdness is part of natural human language. It is all part weirdness of the writing system, which is entirely invented. What we are facing now is difficulties in interfacing different implementations of the same technology (writing).
In the pencil-and-paper era, we had no problems ever with this.
It's only because we tried to 'simplify' things that we ran into problems :-)
As an additional aside, the OP just talked about sorting words within the same language.
What about sorting across languages? (For example, names?)