Proxmap sort
Insertion sorting into buckets during proxmap.
Insertion sorting into buckets during proxmap.
Example of insertion sort sorting a list of random numbers.
ClassSorting algorithm
Data structureArray
Worst-case performance
Best-case performance
Average performance
Worst-case space complexity
Elements are distributed among bins
Unlike bucket sorting which sorts after all the buckets are filled, the elements are insertion sorted as they are inserted

ProxmapSort, or Proxmap sort, is a sorting algorithm that works by partitioning an array of data items, or keys, into a number of "subarrays" (termed buckets, in similar sorts). 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. Keys are placed into each subarray using insertion sort. If keys are "well distributed" among the subarrays, sorting occurs in linear time. The computational complexity estimates involve the number of subarrays and the proximity mapping function, the "map key," used. It is a form of bucket and radix sort.

Once a ProxmapSort is complete, ProxmapSearch can be used to find keys in the sorted array in time if the keys were well distributed during the sort.

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

Overview

Basic strategy

In general: Given an array A with n keys:

Simplied version: Given an array A with n keys

  1. Initialize: Create and initialize 2 arrays of n size: hitCount, proxMap, and 2 arrays of A.length: location, and A2.
  2. Partition: Using a carefully chosen mapKey function, divide the A2 into subarrays using the keys in A
  3. Disperse: Read over A, dropping each key into its bucket in A2; insertion sorting as needed.
  4. Collect: Visit the subarrays in order and put all the elements back into the original array, or simply use A2.

Note: "keys" may also contain other data, for instance an array of Student objects that contain the key plus a student ID and name. This makes ProxMapSort suitable for organizing groups of objects, not just keys themselves.

Example

Consider a full array: A[0 to n-1] with n keys. Let i be an index of A. Sort A's keys into array A2 of equal size.

The map key function is defined as mapKey(key) = floor(K).

Array table
A1 6.7 5.9 8.4 1.2 7.3 3.7 11.5 1.1 4.8 0.4 10.5 6.1 1.8
H 1 3 0 1 1 1 2 1 1 0 1 1
P 0 1 -9 4 5 6 7 9 10 -9 11 12
L 7 6 10 1 9 4 12 1 5 0 11 7 1
A2 0.4 1.1 1.2 1.8 3.7 4.8 5.9 6.1 6.7 7.3 8.4 10.5 11.5

A demonstration of ProxMapSort, a bucket sort variant that uses intermediate parallel arrays to efficiently index and size its sublists.

Pseudocode

// compute hit counts
for i = 0 to 11 // where 11 is n
{
    H[i] = 0;
}
for i = 0 to 12 // where 12 is A.length
{
    pos = MapKey(A[i]);
    H[pos] = H[pos] + 1;
}

runningTotal = 0; // compute prox map – location of start of each subarray
for i = 0 to 11
    if H[i] = 0
        P[i] = -9;
    else
        P[i] = runningTotal;
        runningTotal = runningTotal + H[i];

for i = 0 to 12 // compute location – subarray – in A2 into which each item in A is to be placed
    L[i] = P[MapKey(A[i])];

for I = 0 to 12; // sort items
    A2[I] = <empty>;
for i = 0 to 12 // insert each item into subarray beginning at start, preserving order
{
    start = L[i]; // subarray for this item begins at this location
    insertion made = false;
    for j = start to (<the end of A2 is found, and insertion not made>)
    {
        if A2[j] == <empty> // if subarray empty, just put item in first position of subarray
            A2[j] = A[i];
            insertion made = true;
        else if A[i] < A2[j] // key belongs at A2[j]
            int end = j + 1; // find end of used part of subarray – where first <empty> is
            while (A2[end] != <empty>)
                end++;
            for k = end -1 to j // move larger keys to the right 1 cell
                A2[k+1] = A2[k];
                A2[j] = A[i];
            insertion made = true; // add in new key
    }
}

Here A is the array to be sorted and the mapKey functions determines the number of subarrays to use. For example, floor(K) will simply assign as many subarrays as there are integers from the data in A. Dividing the key by a constant reduces the number of subarrays; different functions can be used to translate the range of elements 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

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.

Having a good MapKey function is imperative for avoiding the worst case. We must know something about the distribution of the data to come up with a good key.

Optimizations

  1. Save time: Save the MapKey(i) values so they don't have to be recomputed (as they are in the code above)
  2. Save space: The proxMaps can be stored in the hitCount array, as the hit counts are not needed once the proxmap is computed; the data can be sorted back into A, instead of using A2, if one takes care to note which A values have been sorted so far, and which not.

JavaScript code implementation:

Array.prototype.ProxmapSort = function()
{//-- Edit date: 2019/11/13 Taiwan --//
  var start = 0;
  var end = this.length;
  var A2 = new Array(end);
  var MapKey = new Array(end);
  var hitCount = new Array(end);
  
  for (var i = start; i < end; i++) { hitCount[i] = 0; }
  var min = this[start];
  var max = this[start];
  for (var i = start+1; i < end; i++) {
    if (this[i] < min) { min = this[i]; }
    else {if (this[i] > max) { max = this[i]; ))
  }
  //Optimization 1.Save the MapKey[i].
  for (var i = start; i < end; i++) {
    MapKey[i] = Math.floor(((this[i] - min ) / (max - min )) * (end - 1));
    hitCount[MapKey[i]]++;
  }
  //Optimization 2.ProxMaps store in the hitCount.
  hitCount[end-1] = end - hitCount[end-1];
  for (var i = end-1; i > start; i--){
    hitCount[i-1] = hitCount[i] - hitCount[i-1];
  }
  //insert A[i]=this[i] to A2 correct position
  var insertIndex = 0;
  var insertStart = 0;
  for (var i = start; i < end; i++) {
    insertIndex = hitCount[MapKey[i]];
    insertStart = insertIndex;
    while (A2[insertIndex] != null) { insertIndex++; }
    while (insertIndex > insertStart && this[i] < A2[insertIndex-1]) {
      A2[insertIndex] = A2[insertIndex-1];
      insertIndex--;
    }
    A2[insertIndex] = this[i];
  }
  for (var i = start; i < end; i++) { this[i] = A2[i]; }
};

Comparison with other sorting algorithms

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.

ProxmapSort allows for the use of ProxmapSearch. Despite the O(n) build time, ProxMapSearch makes up for it with its average access time, making it very appealing for large databases. If the data doesn't need to be updated often, the access time may make this function more favorable than other non-comparison sorting based sorts.

Generic bucket sort related to ProxmapSort

Like ProxmapSort, bucket sort generally operates on a list of n numeric inputs between zero and some maximum key or value M and divides the value range into n buckets each of size M/n. If each bucket is sorted using insertion sort, ProxmapSort and bucket sort can be shown to run in predicted linear time.[1][original research?] However, the performance of this sort degrades with clustering (or too few buckets with too many keys); if many values occur close together, they will all fall into a single bucket and performance will be severely diminished. This behavior also holds for ProxmapSort: if the buckets are too large, its performance will degrade severely.

References

  1. ^ Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0-262-03293-7. Section 8.4: Bucket sort, pp.174–177.