To clarify my "how hard" sentiment - I had in mind that the normal sort function becomes a "function selector" that grabs the user's chosen sort function from their profile, then applies that to the comments.
The difficulty in all this would be policing the kind of code that can be written - perhaps a small DSL that compiles into arc code, or possibly direct arc code that gets vetted by a/some moderators.
The actual sort function seems to be (from arc3.tar, but may well have been changed here... nothing is safe from a REPL!)
EDIT: indeed! see http://news.ycombinator.com/item?id=845932
(def display-subcomments (c user whence (o indent 0))
(each k (sort (compare > frontpage-rank:item) c!kids)
(display-comment-tree (item k) user whence indent)))
so that in itself should not be too hard to modify, and provided it is not that much more complex, I can't see it putting that much more strain on the server. The sort function gets called for each page view, the user's profile (username / logout / threads) gets accessed for each view, so the only thing that needs to be resolved is the specific sort function.
The conversation threading could indeed become a bit fragmented, but then again, each time you look at a story on HN the comments will be in a different order due to the weighting and voting.