In this paper we systematically derive randomized algorithms (both sequential and parallel) for sorting and selection from
basic principles and fundamental techniques like random sampling. We prove several sampling lemmas which will find independent
applications. The new algorithms derived here are the most efficient known. From among other results, we have an efficient
algorithm for sequential sorting.
The problem of sorting has attracted so much attention because of its vital importance. Sorting with as few comparisons as
possible while keeping the storage size minimum is a long standing open problem. This problem is referred to as ‘the minimum
storage sorting’ [10] in the literature. The previously best known minimum storage sorting algorithm is due to Frazer and
McKellar [10]. The expected number of comparisons made by this algorithm is n log n + O(n log log n). The algorithm we derive in this paper makes only an expected n log n + O(n ω(n)) number of comparisons, for any function ω(n) that tends to infinity. A variant of this algorithm makes no more than n log n + O(n log log n) comparisons on any input of size n with overwhelming probability.
We also prove high probability bounds for several randomized algorithms for which only expected bounds have been proven so
far.