Abstract (Arne Andersson)

We give an overview of some recent findings in the area of sorting and searching. In particular, we discuss the relevance of the so-called information theoretic lower bound. Among others, we show that there is a data structure supporting search/update in O(sqrt(log n)) time which is simple enough to be implemented efficiently.

We will also give a short overview of ongoing work to implement new, practical, sorting algorithms.


Last modified: March 7, 1996.
Kim Skak Larsen (kslarsen@imada.sdu.dk)