# Sorting using comparisons that are not simple mappings of simple comparisons

The Python language has a sort(x) function that sorts a list based on the intrinsic comparison operator associated with the type of the elements of its input list x. One can also provide a cmp argument (sort(x, cmp=f)), which is a two-parameter function that will be used to compare pairs of elements of x. In general, the cmp function will be called $$O(len(x) \log len(x))$$ times.

More efficiently, one can provide a key argument (sort(x, key=f)), which will be called $$O(len(x))$$ times to transform each element of x into "key values" which will then be compared by the intrinsic comparison operator associated with the type of the key values.

A developer of the key feature has asserted that using key is always more efficient than using cmp. This leads to a somewhat amorphous atheoretical question:

Does there exist a universe of values $$U$$ which can be compared by a "fast" algorithm but for which there is no "fast" algorithm which maps elements of $$U$$ in an order-preserving way into elements of a "simple" key set $$K$$ which can be compared by a "fast" algorithm? I assume that all the orders are total orders. The exact meaning of "simple" is unclear to me, but my intuition is that "finite sequences of integers under lexicographic ordering" is a superset of all totally-ordered sets that I would consider "simple". The condition of "simplicity" is what excludes the trivial solution of setting $$K = U$$ and using the identity as the key mapping, and the simplicity of $$K$$'s comparison function is what excludes having the key mapping simply encode elements of $$U$$ into $$K$$ in some straightforward way.

In a sense, what I'm looking for is a total ordering which is not a "simple" transformation of "simple" totally-ordered set.