Algorithms for frequency distributions: efficiency and generality comparisons

Five methods for forming empirical frequency distributions are outlined. A specific implementation of each is described, and theoretical comparison of their speed and storage is supplemented by simulation data to give a series of recommendations about the appropriateness of each for different situations. The index method is the fastest of those considered, but often uses excessive space. A method based on height-balanced trees is economical of space, and still has good speed. A method based on Quicksort is faster than the tree method, but uses more space.