adaptive heap sort
Google
Sort algorithms home
JavaCFORTRANPASCAL
sort adaptive heap sort

Also defined at: http://www.nist.gov/dads/HTML/adaptiveHeapSort.html.

Inherits from heapsort, adaptive sort

A variant of heapsort that uses a randomized binary search tree (RBST) to structure the input according to any preexisting order. The RBST is used to select candidates that are put into the heap so the heap doesn't need to keep track of all elements. [National Institute of Standards and Technology]

Author: Nikita Ogievetsky, © Cogitech, Inc. 2002