This is a dream of mine as well, but performance may be a problem. Custom functions mean no caching and arbitrary computational burden from each function.
It doesn't have to be totally custom. Just solicit a few representative types and allow all those. This also solves the problem of not everyone knowing how to write such a function, and dealing with user code running on the server.
Better yet, play around with lots of different sorting methods, and look for patterns in the sorting method used (s), the user's data and history (h), and the amount of money the user ends up spending ($).
Maximize $, and don't ask stupid questions like "Would you rather sort by variance, average rating, or Wilson score?"
(I'm pretty sure that's what Amazon is busy doing every day. They're positively brilliant at turning data into money.)
This only applies if you are using a sub-par database. While caching computationally heavy operations is not always a good choice (since they will need to get updated when more entries are added to the dataset), chances are you will have orders of magnitudes more lookups than writes and hence it makes sense to create a computed column and index the results (and hence cache them).
In the case of Amazon, perhaps the Associates Web Service APIs could allow the creation of tool allowing user-defined sorting functions. I've never used these APIs, but I found some details on them that lead me to think it would be possible. See http://aws.amazon.com/associates/#details
That said, asking honestly, are you entirely convinced of the mass appeal of user-defined (or user-selected) sorting algorithms? I find that the current algorithm usually gives fairly sane results.
I don't see why (outside of security issues) we can't just define our own sorting functions for a site.