PCSC 2008: Dr. Eliezer Albacea

8th Philippine Computing Science Congress (PCSC 2008)
23 - 24 February 2008
University of the Philippines-Diliman
Quezon City, Philippines
Organized by: Computing Society of the Philippines
(CSP)Tel. +63 2 7090907, +63 2 4266125
E-mail: computingsoc@gmail.com
Website: http://www.csp.org.ph/
=================================================

An Almost Optimal Sorting Algorithm

Eliezer A. Albacea, Ph.D.
Director
Institute of Computer Science
University of the Philippines-os Banos
College, Laguna, Philippines
eaalbacea@uplb.edu.ph

Abstract:

Some recent algorithms based on Quicksort exhibit an average number of comparisons of n log n + O(n) . In this paper, we show the existence of an almost optimal sorting algorithm whose average number of comparisons is n log(n + 1) - n + O(1). Thus, this algorithm is quite near the information theoretic lower bound when it comes to the average number of comparisons involved in sorting a sequence of n elements.

Keywords: Samplesort, Quicksort, Leapfrogging Samplesort, minimum-comparison sorting, analysis of algorithms.