procedure search (xintegervar rootword)(adens _list *var wordbegin :rootsentinel key :xif sentinel then (*first element*new(root)root key :xroot count : root next :sentinel elsif key then inc( countelse (*search*repeat : : next until key xif sentinel then (*new entry* :rootnew(root)root key :xroot count : root next : else (*foundnow reorder*inc( count) next : nextw next :rootroot : end end end search the improvement in this search method strongly depends on the degree of clustering in the input data for given factor of clusteringthe improvement will be more pronounced for large lists to provide an idea of how much gain can be expectedan empirical measurement was made by applying the above cross-reference program to short and relatively long text and then comparing the methods of linear list ordering and of list reorganization the measured data are condensed into table unfortunatelythe improvement is greatest when different data organization is needed anyway we will return to this example in sect number of distinct keys number of occurrences of keys time for search with ordering time for search with reordering improvement factor table comparsion of list search methods test test