The name is short for computing a "proximity map," which indicates for each key K the beginning of a subarray where K will reside in the final sorted order.

If keys are "well distributed" among the subarrays, sorting occurs in linear time.

Once a ProxmapSort is complete, ProxmapSearch can be used to find keys in the sorted array in

Both algorithms were invented in the late 1980s by Prof. Thomas A. Standish at the University of California, Irvine.

JavaScript code implementation: Since ProxmapSort is not a comparison sort, the Ω(n log n) lower bound is inapplicable.

[citation needed] Its speed can be attributed to it not being comparison-based and using arrays instead of dynamically allocated objects and pointers that must be followed, such as is done with when using a binary search tree.

average access time, making it very appealing for large databases.

This behavior also holds for ProxmapSort: if the buckets are too large, its performance will degrade severely.