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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.