1
$\begingroup$

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.

$\endgroup$
5
  • 2
    $\begingroup$ 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. $\endgroup$
    – D.W.
    Jan 20 at 7:30
  • $\begingroup$ 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)". $\endgroup$
    – J..y B..y
    Jan 20 at 10:23
  • $\begingroup$ @J..yB..y If we're using comparator functions, we kind of have to do comparisons, don't we? $\endgroup$ Jan 20 at 11:26
  • $\begingroup$ @D.W. Thanks for the pointers, I wasn't familiar with those concepts at all. Question updated. $\endgroup$ Jan 20 at 11:51
  • 2
    $\begingroup$ 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. $\endgroup$
    – D.W.
    Jan 20 at 20:25

1 Answer 1

2
$\begingroup$

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 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).

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).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.