Yeah, I also think this should be present in the core. And actually it is part of the v1.7 backlog, which means (unless there is an unexpected scope change) this feature should be added to the v1.7 release. Anyway, I want to share a few thoughts on this.
The issue about writing this kind of plugin without making core changes and no AJAX calls is that you will only be able to sort questions on a given page. In other words, suppose you have 50 answers for a question, you display 10 answers per page, you are in the second page and the core is configured to display answers by date. If I configure the plugin to sort by highest votes then I will still get exactly all the same answers (11-20 in the date sort) but only those 11-20 sorted by vote.
Or maybe a simpler example, if the core is configured to sort by date and the most voted answer of a question is not in the first page, then I wont' see it if the plugin is set to sort by highest votes.
So this behaviour is a bit unexpected. However, this plugin would still be 100% reliable if you apply a simple rule: you only display the plugin buttons if and only if all the answers for a question fit in the first page. Of course, the downside of applying this rule is that users will sometimes see the buttons and sometimes not, depending on the amount of answer pages.
I just thought sharing this might help on the development :)