The obvious answer of where should sorting operations reside appears to be “in the database, stupid!” RDBMSs are built specifically for this kind of activity. They’re good at it, they’re fast, and if properly indexed, they can sort arbitrarily large sets of data better than just about anything on the planet.
But the answer isn’t always quite so straightforward.
If your dataset is small enough, if your sort criteria is sufficiently complex, if your sorting is over columns that you would not otherwise index, or if your application has a sufficiently large user base, you may actually be better off sorting your data in the application.
The primary problem with today’s relational databases is that they don’t scale out easily. Yes, there are strategies to help deal with this problem; but it’s not nearly as simple as “drop another database server into the farm”. Application servers, on the other hand, are built to do just that. Can’t handle the load, stand up another server. Often, this is less costly than hiring a developer to try to make the application more efficient. And in any event, unless you are using one of the free database servers, adding application servers will be less expensive than adding database servers.
Indexing is supposed to solve our data retrieval performance issues – and for the most part, it does. There is a downside however: each index makes inserts/updates slower. Again, there are strategies for working around this; but they usually entail segregating the tables that written to from those that are read from. The result is that the user is potentially left waiting for an update process to complete before they can read data they just saved. I say, if your only purpose for indexing a column is to improve the performance of a sort operation, move it to the application.
Some sort operations are sufficiently complex to warrant keeping out of the database. For example, if you wanted to sort a list of stores within a certain zip code by their distance from a certain competitor, you are most likely better off doing this in the application layer. There is virtually no way to do this more efficiently in an RDBMS; all you are really doing is ensuring that fewer simultaneous queries can be executed.
One final note: while RDBMS is currently de-rigeur, the industry is moving toward a more agnostic data storage model. It will not always be possible to know that the data is stored relationally; and therefore it may not always be possible to know the sorting characteristics of the data provider. Find this out before making any decision.