2003-46: Adaptive Sorting with AVL Trees

DIMACS TR: 2003-46

Adaptive Sorting with AVL Trees

Author: Amr Elmasry

ABSTRACT A new adaptive sorting algorithm is introduced. The new implementation relies on using the traditional AVL trees, and has the same performance limitations. More precisely, the number of comparisons performed by our algorithm, on an input sequence of length $n$ that has $I$ inversions, is at most 1.44nlg(I/n) + O(n). Empirical results imply an average performance of about 1.02nlg(I/n) comparisons for random sequences. Our algorithm runs in time O(nlg(I/n)) and is practically efficient and easy to implement.

Paper available at ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/2003/2003-46.ps.gz

DIMACS Home Page