The major issue, as I see it, is with "permanently." As Wes Miller points out, you can use the Sort tool that will sort a dataset into a new dataset, but is that sorting "permanent?" The Sort tool creates a point-in-time sorted dataset, it doesn't create a dataset that will forever remain sorted the same as the data is modified over time.
The relational model, from which relational DBMSes are founded, is based on set theory and predicate logic. Since mathematical sets are unordered collections of distinct/unique objects, sorting is more an issue of displaying the data rather than storing the data. Granted there is sorting of data within DBMSes, like Clustered Indexes in SQL Server or certain other indexes in other systems, but this type of sorting or need for it is driven by implementation/performance issues. One of the beauties of the SQL SELECT statement is that it allows people to view information in a way that makes sense to them, not based on other peoples' assumptions of how the data should or shouldn't be stored.
If your question is more about changing the default sort order in ArcGIS than creating a new, sorted data snapshot; unfortunately, I don't have an answer for you. The question of changing the default sort order for layers and views in ArcGIS has been around for a long time, and I haven't seen a complete solution. One can sort a layer or view and export a layer file that will maintain that sort, at least for a while until the data starts getting modified by other users.
