in the bucket). Total time is the number of buckets, (n/c), times = . 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 Save time: Save the MapKey(i) values so they don't have to be recomputed (as they are in the code above) 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. 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