I'm not sure about the intricacies, but I think table.sort() will do it. The doc I'm looking at is here (
http://lua-users.org/wiki/TableLibraryTutorial), but it doesn't say anything about behavior for non-numerical keys, and I'm here at work, so no way to test right now.
If table.sort() by itself doesn't do it, you might be able to make it work properly with a custom sorting function, based on the example in the table.sort entry in the doc linked above.
I would be wary of using table keys as data, though. The whole point of keys being any data type is to make lookups easier. You might try making two tables and synchronizing their sort, however.
Good luck!