It "pays" when the cost of pre-computing the sort keys for all of your elements is significantly less than re-computing the sort keys each time you make a comparison.

Well, in most of those cases, it pays to use the Gutman-Rossler Transform.