DEPARTMENT OF MATHEMATICS AND COMPUTER SCIENCE               
                              ODENSE UNIVERSITY                              

             Faster Sorting and Searching in Theory and Practice             

                                Arne Andersson                               
                        Department of Computer Science                       
                               Lund University                               

                     Tuesday, March 19, 1996, at 2:15 PM                     
                               The Seminar Room                              


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.


                                                               Joan F. Boyar