Donald Bren School of Information and Computer Sciences

Algorithms that modify the order of linear search lists are surveyed. First the problem, including assumptions and restrictions, is defined. Next a summary of analysis techniques and measurements that apply to these algorithms is given. The main portion of the paper presents algorithms in the literature with absolute analyses where available. The following section gives relative measures which are applied between two or more algorithms. The final section presents open questions.