in A to subarrays, such as converting the letters A–Z to 0–25 or returning the first character (0–255) for sorting strings. Subarrays are sorted as the data comes in, not after all data has been placed into the subarray, as is typical in bucket sorting. Proxmap searching ProxmapSearch uses the proxMap array generated by a previously done ProxmapSort to find keys in the sorted array A2 in constant time. Basic strategy Sort the keys using ProxmapSort, keeping the MapKey function, and the P and A2 arrays To search for a key, go to P[MapKey(k)], the start of the subarray that contains the key, if that key is in the data set Sequentially search the subarray; if the key is found, return it (and associated information); if find a value greater than the key, the key is not in the data set Computing P[MapKey(k)] takes time. If a map key that gives a good distribution of keys was used during the sort, each subarray is bounded above by a constant c, so at most c comparisons are needed to find the key or know it is not present; therefore ProxmapSearch is . If the worst map key was used, all keys are in the same subarray, so ProxmapSearch, in this worst case, will require comparisons. Pseudocode function mapKey(key) is return floor(key) proxMap ← previously generated proxmap array of size n A2 ← previously sorted array of size n function proxmap-search(key) is for i = proxMap[mapKey(key)] to length(array) − 1 do if sortedArray[i].key == key then return sortedArray[i] Analysis Performance Computing H, P, and L all take time. Each is computed with one pass through an array, with constant time spent at each array location. Worst case: MapKey places all items into one subarray, resulting in a standard insertion sort, and time of . Best case: MapKey delivers the same small number of items to each subarray in an order where the best case of insertion sort occurs. Each insertion sort is , c the size of the subarrays; there are p subarrays thus p * c = n, so the insertion phase take O(n); thus, ProxmapSort is . Average case: Each subarray is at most size c, a constant; insertion sort for each subarray is then O(c^2) at worst – a constant. (The actual time can be much better, since c items are not sorted until the last item is placed