I think you might find this application of ST will actually slow down the sort. As you said, it helps if the key is expensive to computer.

You also said ST is more likely to help for long lists, but that's not true. It loses effectiveness as the list grows.