Efficient and simple randomized algorithms where determinism is difficult
Sorting nuts and bolts

The following problem was suggested by Rawlins in 1992:  Suppose you are given a collection of n nuts and n bolts.  Each bolt fits exactly one nut, and otherwise, the nuts and bolts have distinct sizes.  The sizes are too close to allow direct comparison between pairs of bolts or pairs of nuts.  However, you can compare any nut to any bolt by trying to screw them together; in constant time, you will discover whether the bolt is too large, too small, or just right for the nut.  Your task is to discover which bolt fits each nut, or equivalently, to sort the nuts and bolts by size.

A straightforward variant of randomized quicksort solves the problem in $O(n \log n)$ time with high probability.  Pick a random bolt; use it to partition the nuts; use the matching nut to partition the bolts; and recurse.  However, finding a deterministic algorithm that even runs in $o(n^2)$ is nontrivial.  Deterministic $O(n\log n)$-time algorithms were finally found in 1995 by Bradford and independently by Komlós, Ma, and Szemerédi.  Under the hood, both algorithms use variants of the AKS parallel sorting network, so the hidden constant in the $O(n\log n)$ time bound is quite large; the hidden constant for the randomized algorithm is 4.


Noga Alon, Manuel Blum, Amos Fiat, Sampath Kannan, Moni Noar, and Rafail Ostrovsky. Matching nuts and bolts. Proc. 5th Ann. ACM-SIAM Symp. Discrete Algorithms, 690–696, 1994.
Noga Alon, Phillip G. Bradford, and Rudolf Fleischer. Matching nuts and bolts faster. Inform. Proc. Lett. 59(3):123–127, 1996.
Phillip G. Bradford. Matching nuts and bolts optimally. Tech. Rep. MPI-I-95-1-025, Max-Planck-Institut für Informatik, 1995. http://domino.mpi-inf.mpg.de/internet/reports.nsf/NumberView/1995-1-025
Phillip G. Bradford and Rudolf Fleischer. Matching nuts and bolts faster.  Proc. 6th. Int. Symp. Algorithms Comput., 402–408, 1995. Lecture Notes Comput. Sci. 1004.
János Komlós, Yuan Ma, and Endre Szemerédi. Matching nuts and bolts in $O(n\log n)$ time. SIAM J. Discrete Math. 11(3):347–372, 1998.
Gregory J. E. Rawlins. Compared To What? : An Introduction to The Analysis of Algorithms. Computer Science Press/W. H. Freeman, 1992.