Может, проще отправлять каждый раз на сервер критерий сортировки, делать соответствующий запрос к базе и получать каждый раз требеумую выборку? Думаю, запрос аджаксом и небольшой трафик туда-сюда не кретичен?

Ну, если десяток-два строк будет в таблице, то конечно, можно и клиентом посортировать ... нема базара.
Но к сожалению так бывает не всегда. Часто надо отобразить данные с о-о-очень большой таблицы. Естественно, всю таблицу не передают - делается постраничное отображение с навигацией. И когда, к примеру, отображена 34 страница из 200 и захотелось сделать другую сортировку, то НИЧЕГО, кроме как через сервер, не сделаешь.

Поэтому просто считаю, что вопрос сформулирован неправильно, так как много его трактовок. Правильнее было бы просто сказать, что на странице есть таблица, у которой надо сделать сортировку столбцов. А в данной формулировке все же ответы неоднозначны.

Кстати, прошлая ссылка мне не очень понравилась - видел где-то более изящную сортировку (извините, не помню).

Даже приведу пример ...
К этому посту прикреплено два фрагмента одной страницы (извините за качество, но можно только 100Кб прикрепить). Как видно, таблица есть, данные есть, но сортировка по алфавиту любого столбца мне как пользователю до лампочки, так как эта сортировка в пределах диапазона, отображенного данной таблицей, не будет удовлетворять моим требованиям - мне нужно в пределах всей таблицы базы данных.
Поэтому вариант у меня только один - через сервер и запросы к БД. А чем мой вопрос сильно отличается от начального?