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). 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