No discussion of making ST more efficient would be complete without mentioning the Guttman-Rosler Transform. GRT is similar to your idea, except it modifies the representation of the data (using pack and unpack) to use less memory or to make the sort simpler.