Array size: number of buckets in the proximity map.

Hit count: count of items that hashed to a particular bucket.

Location: Location[x] correlates to a record in Data[x]; but this stores which hash bucket the element belongs to.

Proximity map: Holds the first index (of the Data array) for an element that hashes to this bucket. Elements defined in ProxMap[x] have an above zero value in HitCount[x]

Data: array which holds the elements within the map

Step 1: initialize memory, helper arrays.

Step 2: hash members of unsorted array to find the buckets they will belong to and count memberships

Step 3: insertion sort elements of the unsorted array to their neighborhood in the sorted array

• Wikiedia
• College paper on ProxMap sorting

Hashing

ProxMaps want a hash function where keys can be kept in ascending order as well as spread evenly across the buckets.

The college paper uses a technique:

• Convert all keys to integers
• Find the highest and lowest integers
• Convert all keys to a float in the range of [0, 1] based on the highest and lowest integer
• Round the floats