Philipp. Sci. Lett. 2012 5 (1) 014-016

available online: January 30, 2012

*Corresponding author

Email Address: eaalbacea@uplb.edu.ph

Submitted: December 6, 2011

Accepted: December 27, 2011

Average-case analysis of Leapfroggingsamplesort

by Eliezer A. AlbaceaInstitute 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