There are several approaches to sorting marked-up structures like HTML tables. Generally declarative approaches are preferred, as they can be implemented in multiple languages and contexts and are often amenable to optimizations.
One approach is to add a sort key to each table cell. The keys are always compared (say) as strings using the HTML ASCIIlower collation. This means you can either do the sorting server-side or map values to a surrogate key for sorting when generating the markup.
Another approach is to supply a function at runtime; this can either be a comparison function, as in languages like C, or it could generate a surrogate key for each entry, a string, and the implementation then sorts those. In some cases the surrogate keys can be integers and an O(1) radix sort can be used, but at the cost of slightly more memory to store all the keys.
This reasoning leads to wanting something like
<td sortkey="Saint John Stevas, Norman">Norman St John Stevas</td>
Identifying which columns to sort, and which rows to move, especially in the presence of spans, is tricky, although simply saying that tables with spans outside the headers can’t be sorted is probably an acceptable first cut. So a sortable attribute that can have values of ascending, descending, none or sticky (where none means you can’t click on the heading to sort the column and sticky means the entries in the column don’t move when the table is sorted, e.g. for row numbers) may be sufficient.
It would be nice if any table with a “regular” structure could be sorted by default; it’d also be nice if, like some Braille systems, most user agents allowed transposition of regular tables by default.