VOLUME 5 NUMBER 1 (January to June 2012)

by Eliezer A. Albacea

Institute of Computer Science, University of the Philippines Los Baños
College, Laguna, Philippines

The leapfrogging samplesort was introduced in1995 but was not analyzed completely. In thispaper, we analyze the algorithm in terms ofexpected number of comparisons. In particular,we obtain an estimated expected number ofcomparisons of n [ log (n+1)] - 2 ^{[ log (n+1) ]} - n + [ log (n+1) ]+ 1 comparisons using the assumption that we estimate insteadthe cumulative distribution function of the input sequence from asample. It should be noted that the results obtained in this paperis an estimate of the true expected number of comparisons. Theproblem of getting the true expected number of comparisonsremains open.