There are several generic sorting algorithms available that are highly optimized and are provided as part of standard programming libraries, such as the qsort implementation of quicksort available through the C standard library. In this work we present a practical algorithmic transformation that uses random sampling and ordered search, that can convert an existing implementation of any sorting algorithm X into a sorting algorithm Y of higher observed efficiency but which still utilizes X for sorting. The resulting algorithm Y is a randomized algorithm of faster running time with high probability. Experimental results based on an implementation of the transformation support the efficiency claim. The transformation could be used as a wrapper for sorting implementations to increase their efficiency and to eliminate the spikes of poor performance of such implementations for certain input instances.
All Science Journal Classification (ASJC) codes
- Computer Science(all)