Using difficulty of prediction to decrease computation: Fast sort, priority queue and convex hull on entropy bounded inputs

There is an upsurge in interest in the Markov model and also more general stationary ergodic stochastic distributions in theoretical computer science community recently (e.g. see [Vitter, Krishnan91], [Karlin, Philips, Raghavan92], [Raghavan92] for use of Markov models for on-line algorithms, e.g., cashing and prefetching). We have implemented the sequential version of a sorting algorithm on SPARC-2 machine and compared to the UNIX system sorting routine -quick sort. We found that our algorithm beats quicksort for large n on extrapolated empirical data. Our algorithm is even more advantageous in applications where the keys are many words long.

Duke Scholars

Author John H. Reif Computer Science