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


Journal Article

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 Authors

Cited Authors

  • Chen, S; Reif, JH

Published Date

  • December 1, 1993

Published In

Start / End Page

  • 104 - 112

International Standard Serial Number (ISSN)

  • 0272-5428

Citation Source

  • Scopus