Increasing the efficiency of existing sorting algorithms by using randomized wrappers

Alexandros V. Gerbessiotis, Constantinos J. Siniolakis

Research output: Contribution to journalArticlepeer-review

Abstract

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.

Original languageEnglish (US)
Pages (from-to)498-504
Number of pages7
JournalComputer Journal
Volume46
Issue number5
DOIs
StatePublished - Jan 1 2003

All Science Journal Classification (ASJC) codes

  • Computer Science(all)

Fingerprint Dive into the research topics of 'Increasing the efficiency of existing sorting algorithms by using randomized wrappers'. Together they form a unique fingerprint.

Cite this