Alexandros V. Gerbessiotis and Constantinos J Siniolakis Abstract:
In this work we present an algorithmic transformation, that given two algorithms implementing respectively, sorting and searching, provides a randomized sorting algorithm that with high probability requires less time than the original sorting algorithm.
This claim is true for a wide range of the parameters that describe the running time of the procedures for sorting and searching.