9
$\begingroup$

Inspired by this question in which the asker wants to know if the running time changes when the comparator used in a standard search algorithm is replaced by a fair coin-flip, and also Microsoft's prominent failure to write a uniform permutation generator, my question is thus:

Is there a comparison based sorting algorithm which will, depending on our implementation of the comparator:

  1. return the elements in sorted order when using a true comparator (that is, the comparison does what we expect in a standard sorting algorithm)
  2. return a uniformly random permutation of the elements when the comparator is replaced by a fair coin flip (that is, return x < y = true with probability 1/2, regardless of the value of x and y)

The code for the sorting algorithm must be the same. It is only the code inside the comparison "black box" which is allowed to change.

$\endgroup$
  • $\begingroup$ See also this question. $\endgroup$ – Raphael Mar 20 '13 at 21:12
  • 2
    $\begingroup$ See also the following interesting question: cstheory.stackexchange.com/questions/5321/…. $\endgroup$ – Yuval Filmus Mar 21 '13 at 0:35
  • 1
    $\begingroup$ Do you want your random comparator to be be well-behaved? Here are two possible ways. (1) Once the comparator makes up its mind that $x<y$, then $x<y$ always, and also $y>x$. (2) Same, but if furthermore the comparator decides that $x<y$ and $y<z$, then it commits to $x<z$ (and $z>x$). In both cases, each unconstrained query is still completely random. $\endgroup$ – Yuval Filmus Mar 21 '13 at 5:45
  • $\begingroup$ @YuvalFilmus I want essentially what is asked for in your linked question, except that the same circuit should also sort if we replace the random gate with a compare-exchange gate that orders the pair of elements. $\endgroup$ – Joe Mar 21 '13 at 20:43
  • 1
    $\begingroup$ See here for nice visualisations. $\endgroup$ – Raphael Jun 30 '14 at 9:34
3
$\begingroup$

The following deterministic (without the comparator) algorithm works for an input tuple $(a_1,\dots,a_n)$:

  1. Do the Fisher-Yates shuffle using your comparator with some static pair (say $a_1 < a_2$) as a coin flip (doing acceptance-rejection sampling). If the comparator outputs $1$ the first time, use it inverted to avoid an endless rejection loop in the deterministic case.
  2. (optional speedup: Try a single pair $n$ times, where $n$ is the length or your input. If any two of the outputs differ return the permutation obtained in (1))
  3. Sort your array using merge sort.

Given a deterministic order relation as comparator this algorithm sorts an array in time $\mathcal{O}(n \log n)$ since the Fisher-Yates shuffle runs in $\mathcal{O}(n)$ using maximal $\mathcal{O}(\log n)$ nonrandom "random bits" (e.g. calls to your comparator) in each step and merge sort has the same asymptotic complexity. The result of (1) is totally useless in this case, but since it's followed by a real sort, this does no harm.

Given a real coin flip as comparator (1) permutes the array with equal probability for each permutation and if you really have to do (3) (you left out (2) or (2) failed to determine the randomness), this is no harm because the distribution of its result only depends on the order of its input which is uniformly distributed among all permutations because of (1), so the result of the entire algorithm is also uniformly distributed. The number of times each acceptance-rejection sampling has to be repeated is geometrically distributed (reject with probability $< \frac{1}{2}$) and therefore it has an expected value $< 2$. Each repetition uses at most $\log n$ bits, so the runtime analysis is nearly the same as in the deterministic case, but we only get an expected runtime of $\mathcal{O}(n \log n)$, with the possibility of nontermination (terminates only almost surely).


As Joe pointed out: If you don't like the test for the first bit in (1), do (3) then (1) and use $a_n < a_1$ which is always $0$, since the array is already sorted in the deterministic case. Additionally you have to subtract your random number from the upper bound on the range in the loop, because the upper bound for the random number yields the identical permutation. But be aware that (2) is forbidden then, because you always have to do the shuffle in the ransom case.


You can even use the same calls to your comparator for (1) and (3), but then proving that the result is uniformly distributed is at least a lot harder, if possible at all.


The following algorithm is has no distinct phases to shuffle and sort, but is asymptotically slower. It's essentially insertion sort with binary search. I will use $a=(a_1,\dots,a_n)$ to denote the input and $b_k=(b_{k,1},\dots,b_{k,k})$ to denote the result after the $k$-th round:

  1. Set $b_{1,1} = a_1$
  2. If $a_2 < a_1$ then $b_2 = (a_2,a_1)$ and $(c,d):= (2,1)$ else $b_2 = (a_1,a_2)$ and $(c,d):= (1,2)$. In either case $a_d < a_c$ will always be $0$ (i.e. false) for a nonrandom comparator.
  3. To obtain $b_{k}$ for $k \geq 3$ obtain $b_{k-1}$ first.
  4. Let $l=\lceil log_2 k \rceil$ and $k' = 2^l$, i.e. $k'$ is the least power of $2$ not smaller than $k$.
  5. Let $i_0 = 0$. For every $j \in \{1,\dots,l\}$ let $$i_j = \begin{cases} i_{j-1} + 2^{l-j} & i_{j-1} + 2^{l-j} > k-1 \wedge a_d < a_c\\ i_{j-1} & i_{j-1} + 2^{l-j} > k-1 \wedge \neg (a_d < a_c)\\ i_{j-1} + 2^{l-j} & i_{j-1} + 2^{l-j} \leq k-1 \wedge b_{k-1,i_{j-1} + 2^{l-j}} < a_k \\ i_{j-1} & i_{j-1} + 2^{l-j} \leq k-1 \wedge \neg(b_{k-1,i_{j-1} + 2^{l-j}} < a_k) \\ \end{cases}$$
  6. If $i_l > k$ repeat (5.) else $b_k=(b_{k-1,1},\dots,b_{k-1,i_l -1},a_k,b_{k-1,i_l},\dots,b_{k-1,k-1})$
  7. Output $b_n$

Random case: 5 + the if clause of 6 is essentially acceptance-rejection sampling. The rest of the algorithm is a naive shuffle: shuffle the first $k-1$ elements and add the $k$-th element to each position with equal probability. If we used the normal insertion sort, we would get a binomial distribution instead.

Note that this algorithm is inefficient in both modes compared to the Fisher-Yates shuffle and merge sort as inserting an element to an arbitrary position is expensive if using an array and binary search needs linear time if using a list. But perhaps a modification of heap sort or tree sort in a similar way could lead to a faster algorithm.

$\endgroup$
  • $\begingroup$ @Joe can you put all your points still valid for the post in the current shape into one comment and delete the rest? $\endgroup$ – frafl Mar 21 '13 at 20:50
  • $\begingroup$ I was hoping for an algorithm that doesn't do different steps depending on which comparator is used. Can you avoid an infinite rejection-loop without probing the comparator? I think you could avoid rejection by performing step (3) first... $\endgroup$ – Joe Mar 21 '13 at 21:05
  • $\begingroup$ What if you do the sorting step, then do the shuffle, but use a sequence of comparisons which depend on the index $i$, so that in the deterministic case, you get the index of the element (no swap), and it remains sorted, but in the random case you perform the standard shuffle with rejection sampling. $\endgroup$ – Joe Mar 21 '13 at 21:11
  • $\begingroup$ First comment: Note that I don't throw away that first sample bit, it's "dual use". I thought about inverting every 2nd bit, but that would not prevent the endless loop. In fact some irregular pattern is needed and even may reject a lot more entries. Of course I could XOR the two most recent bits instead of the first and the most recent, but that's not really different. $\endgroup$ – frafl Mar 21 '13 at 21:31
  • $\begingroup$ Second Comment: The order (1) vs. (3) is only important if you use step (2), because in the random case you have to assure that the shuffle is done with probability 1 otherwise the uniform distribution will be violated. Why should it depend on $i$? In this case $a_n < a_1$ will always answer $0$, which is all we need. $\endgroup$ – frafl Mar 21 '13 at 21:42
4
$\begingroup$

No, this is impossible unless $n \leq 2$. The probability that a permutation is generated by your algorithm using a random comparator is dyadic, i.e. of the form $A/2^B$, whereas the probability should be $1/n!$. When $n > 2$, there is no way to write $1/n!$ in the form $A/2^B$.

$\endgroup$
  • 1
    $\begingroup$ But this only holds, if we need a deterministic bound on the runtime, which was not requested in the question. If we only require the expected runtime to be finite, this should be no problem. $\endgroup$ – frafl Mar 21 '13 at 1:34
  • 1
    $\begingroup$ Are you aware of any reasonable sorting algorithm which doesn't terminate in polynomial time? $\endgroup$ – Yuval Filmus Mar 21 '13 at 1:37
  • 2
    $\begingroup$ You mix the deterministic and random case. The algorithm may terminate in deterministic polynomal time if called with a deterministic order relation and in expected polynomial time if called with a coin as comparator. $\endgroup$ – frafl Mar 21 '13 at 8:43
  • $\begingroup$ @YuvalFilmus why does the decision tree have to have $2^k$ leaves? $\endgroup$ – Joe Mar 22 '13 at 0:21
  • $\begingroup$ If you're doing up to $k$ comparisons in total, then the probability of any event is going to be of the form $A/2^k$. It's not about the number of leaves. The only way out is, as frafl suggests, having an unbounded number of comparisons. $\endgroup$ – Yuval Filmus Mar 22 '13 at 2:15

Your Answer

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

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