Publications [#236953] of John H. Reif

Journal articles or Book chapters PUBLISHED

1. Chen, S; Reif, JH, Using difficulty of prediction to decrease computation: Fast sort, priority queue and convex hull on entropy bounded inputs, Annual Symposium on Foundatons of Computer Science Proceedings (December, 1993), pp. 104-112
   (last updated on 2026/01/15)

   Abstract:
   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.