counts the number of items for each bucket in an auxiliary array, and then makes a running total so each auxiliary entry is the number of preceding items. The second pass puts each item in its proper bucket according to the auxiliary entry for the key of that item. The last pass sorts each bucket. Practice Interpolation sort implementation JavaScript code: Array.prototype.interpolationSort = function() { var divideSize = new Array(); var end = this.length; divideSize[0] = end; while (divideSize.length > 0) { divide(this); } // Repeat function divide to ArrayList function divide(A) { var size = divideSize.pop(); var start = end - size; var min = A[start]; var max = A[start]; for (var i = start + 1; i < end; i++) { if (A[i] < min) { min = A[i]; } else { if (A[i] > max) { max = A[i]; } } } if (min == max) { end = end - size; } else { var p = 0; var bucket = new Array(size); for (var i = 0; i < size; i++) { bucket[i] = new Array(); } for (var i = start; i < end; i++) { p = Math.floor(((A[i] - min ) / (max - min ) ) * (size - 1 )); bucket[p].push(A[i]); } for (var i = 0; i < size; i++) { if (bucket[i].length > 0) { for (var j = 0; j < bucket[i].length; j++) { A[start++] = bucket[i][j]; } divideSize.push(bucket[i].length); } } } } }; Interpolation sort recursive method Worst-case space complexity : Array.prototype.interpolationSort= function() {//-- Edit date:2019/08/31 --// var start = 0; var size = this.length; var min = this[0]; var max = this[0]; for (var i = 1; i < size; i++) { if (this[i] < min) { min = this[i]; } else {if (this[i] > max) { max = this[i];} } } if (min != max) { var bucket = new Array(size); for (var i = 0; i < size; i++) { bucket[i] = new Array(); } var interpolation = 0; for (var i = 0; i < size; i++) { interpolation = Math.floor(((this[i] - min) / (max - min)) * (size - 1)); bucket[interpolation].push(this[i]); } for (var i = 0; i < size; i++) { if (bucket[i].length > 1) { bucket[i].interpolationSort(); } // Recursion for (var j = 0; j < bucket[i].length; j++) { this[start++] = bucket[i][j]; } } } }; Histogram sort implementation Array.prototype.histogramSort