Well, apearently, server side sorting was already implemented by Ilohamail! I used the api so it is enabled in RC as well. The performance is the performance I am looking for and as far as I can see, everything now just works!!
If the server does not implement server side sorting, the current method of sorting is used automaticly. (untested)