# Can arbitrary comparator be transformed into equivalent key for radix sort?

The question is quite simple: Is it possible for any deterministic comparator of keys to be transformed into radix-sortable key mapping function?

By that I mean, does for every comparator C(key) exist a function M(key) such that sorting by C gives the same result as radix-sorting by the output of M?

In hardware, everything has to be an arithmetic comparison (or sequence of) in the end, so if we can prove all comparators are a composition of some simple base case... It seems like it should be a simple proof, but I can't quite put it together.

EDIT: Most sorting algorithms already assume a total order, so let's assume the same.

Note: This question is a more focused version of this question on StackOverflow, since it seems to fit here more.

• Please edit your post to specify what properties you are willing to assume/promise the comparator has. Transitive? Antisymmetric? Reflexive? A partial order? Total order? See en.wikipedia.org/wiki/Homogeneous_relation, en.wikipedia.org/wiki/Partially_ordered_set#Formal_definition, en.wikipedia.org/wiki/Total_order. The answer depends on what you assume.
– D.W.
Jan 20 at 7:30
• Countiing Sort, Radix Sort and various parallel sorting algorithms are counter examples to your assertion that "everything has to be an arithmetic comparison (or sequence of)". Jan 20 at 10:23
• @J..yB..y If we're using comparator functions, we kind of have to do comparisons, don't we? Jan 20 at 11:26
• @D.W. Thanks for the pointers, I wasn't familiar with those concepts at all. Question updated. Jan 20 at 11:51
• Please don't use "EDIT:". Instead, revise the question so it reads well for someone who encounters this for the first time. Don't just append more information. Incorporate it into the flow of the question in a way that is appropriate from a holistic sense. See cs.meta.stackexchange.com/q/657/755.
– D.W.
Jan 20 at 20:25

does for every comparator C(key) exist a function M(key) such that sorting by C gives the same result as radix-sorting by the output of M?

When the domain of values considered is finite (e.g. from 0 o 255), there are (sorting, among others) algorithms which do not use arithmetic comparisons, such as Counting Sort and Radix Sort: you can sort an array $$A$$ of values from a discrete domain (e.g. $$\{0,1,...,d-1\}$$) without comparisons, using merely counters (e.g. $$C[A[i]]++$$) to count the number of occurrences of each value and then produce a sorted array without any data comparisons (you still use comparisons for indices).