<blockquote>
<p>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?</p>
</blockquote>
<p><strong>SHORT ANSWER</strong></p>
<p>Not for non discrete value domains, but yes for discrete value domains.</p>
<p><strong>LONG ANSWER</strong></p>
<p>This is true <strong>only for discrete domains</strong> (which you could argue is always true for a given hardware, but is not a given when developing algorithms which will run on arbitrary hardware yet to invent).</p>
<p>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   <a href="https://en.wikipedia.org/wiki/Counting_sort" rel="nofollow noreferrer">Counting Sort</a> and <a href="https://en.wikipedia.org/wiki/Radix_sort" rel="nofollow noreferrer">Radix Sort</a>: you can sort an array <span class="math-container">$A$</span> of values from a discrete domain (e.g. <span class="math-container">$\{0,1,...,d-1\}$</span>) without comparisons, using merely counters (e.g. <span class="math-container">$C[A[i]]++$</span>) 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).</p>
<p>When the domain of the values is very large, the cost of such techniques becomes prohibitive compared to that of comparison based sorting algorithms, and even if you would be able to find a function M(key) equivalent to comparison function C(key1,key2) such that sorting by C gives the same result as radix-sorting by the output of M, the cost of both algorithms would be quite different.</p>
<p>When the domain of the values is unknown and unbound, you will still be able to sort using comparisons, but not using an arbitrary mapping function (which is the counter example to your statement).</p>

CC BY-SA 4.0
2024-01-21T11:41:25.157Z
2024-01-21T11:41:25.157Z
J.y B.y
<p>The question is quite simple: <strong>Is it possible for any deterministic comparator of keys to be transformed into radix-sortable key mapping function?</strong></p>
<p>By that I mean, does for every comparator <code>C(key)</code> exist a function <code>M(key)</code> such that sorting by <code>C</code> gives the same result as radix-sorting by the output of <code>M</code>?</p>
<p>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.</p>
<p>EDIT: Most sorting algorithms already assume a total order, so let's assume the same.</p>
<p><em>Note: This question is a more focused version of <a href="https://stackoverflow.com/questions/77462547/can-arbitrary-comparator-be-transformed-into-equivalent-key-for-radix-sort">this</a> question on StackOverflow, since it seems to fit here more.</em></p>

CC BY-SA 4.0
2024-01-20T07:30:21.377Z
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 https://en.wikipedia.org/wiki/Homogeneous_relation, https://en.wikipedia.org/wiki/Partially_ordered_set#Formal_definition, https://en.wikipedia.org/wiki/Total_order.  The answer depends on what you assume.
D.W.
CC BY-SA 4.0
2024-01-20T10:23:42.003Z
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)".
J.y B.y
CC BY-SA 4.0
2024-01-20T11:26:09.530Z
@J..yB..y If we're using comparator functions, we kind of have to do comparisons, don't we?
Kryštof Vosyka
CC BY-SA 4.0
2024-01-20T11:51:58.447Z
@D.W. Thanks for the pointers, I wasn't familiar with those concepts at all. Question updated.
Kryštof Vosyka
CC BY-SA 4.0
2024-01-20T20:25:24.567Z
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 https://cs.meta.stackexchange.com/q/657/755.
D.W.
<sorting>
Can arbitrary comparator be transformed into equivalent key for radix sort?
Kryštof Vosyka
# Can arbitrary comparator be transformed into equivalent key for radix sort?

(Asked by: username_0 on 2024-01-20)

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](https://stackoverflow.com/questions/77462547/can-arbitrary-comparator-be-transformed-into-equivalent-key-for-radix-sort) question on StackOverflow, since it seems to fit here more.*

**Tags:** sorting

> **Comments:**
> **username_1**: 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 https://en.wikipedia.org/wiki/Homogeneous_relation, https://en.wikipedia.org/wiki/Partially_ordered_set#Formal_definition, https://en.wikipedia.org/wiki/Total_order.  The answer depends on what you assume.  
> **username_2**: 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)".  
> **username_0**: @J..yB..y If we're using comparator functions, we kind of have to do comparisons, don't we?  
> **username_0**: @username_1 Thanks for the pointers, I wasn't familiar with those concepts at all. Question updated.  
> **username_1**: 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 https://cs.meta.stackexchange.com/q/657/755.  

---

## 1 answers

### Answer by username_2 on 2024-01-21. Score: 2 | Accepted answer

> 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?

**SHORT ANSWER**

Not for non discrete value domains, but yes for discrete value domains.

**LONG ANSWER**

This is true **only for discrete domains** (which you could argue is always true for a given hardware, but is not a given when developing algorithms which will run on arbitrary hardware yet to invent).

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](https://en.wikipedia.org/wiki/Counting_sort) and [Radix Sort](https://en.wikipedia.org/wiki/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).

When the domain of the values is very large, the cost of such techniques becomes prohibitive compared to that of comparison based sorting algorithms, and even if you would be able to find a function M(key) equivalent to comparison function C(key1,key2) such that sorting by C gives the same result as radix-sorting by the output of M, the cost of both algorithms would be quite different.

When the domain of the values is unknown and unbound, you will still be able to sort using comparisons, but not using an arbitrary mapping function (which is the counter example to your statement).


---

