vol. 5 | no. 1 | 2012

published online January 30, 2012

ARTICLE

Average-case analysis of Leapfrogging samplesort

Institute of Computer Science, University of the Philippines Los Baņos

College, Laguna, Philippines

The leapfrogging samplesort was introduced in
1995 but was not analyzed completely. In this
paper, we analyze the algorithm in terms of
expected number of comparisons. In particular,
we obtain an estimated expected number of
comparisons of n [ log (n+1)] - 2 ^{[ log (n+1) ]} - n + [ log (n+1) ]
+ 1 comparisons using the assumption that we estimate instead
the cumulative distribution function of the input sequence from a
sample. It should be noted that the results obtained in this paper
is an estimate of the true expected number of comparisons. The
problem of getting the true expected number of comparisons
remains open.

Email Address:

eaalbacea@uplb.edu.ph

Submitted: December 6, 2011

Accepted: December 27, 2011

Published: January 30, 2012

Editor-in-charge: Amador C. Muriel

Reviewer:

Amador C. Muriel