Quote: linear probing sort for uniformly distributed elements; hash into range and shift as needed

Quotation Skeleton

To sort n elements, the linear probing sort … [Gonnet, G.H., Munro, J.I., Journal of Algorithms, 1984], uses a table of size m, m=n/.alpha. … The elements to be sorted are assumed to … is found by the use of a mapping … If there is a conflict in a position, … this is resolved by letting the element with … As a final step a compaction of the … A suggestion in their paper is to choose … [the size of the overflow area for the last elements] = 106. This yields 4.25 probes on the average and … will occur with a probability less than 10^-20. …   Google-1   Google-2

Copyright clearance needed for quotation.

Related Topics

Topic: sort algorithms (24 items)
Topic: probability (21 items)