{ A[start++] = Bucket[i][j]; } } } } } // Algorithm step-6 }; In-place Interpolation Tag Sort The in-place interpolation tag sort is an in-place algorithm of interpolation sort. In-place Interpolation Tag Sort can achieve sorting by only N times of swapping by maintaining N bit tags; however, the array to be sorted must be a continuous integer sequence and not repeated, or the series is completely evenly distributed to approximate The number of arithmetical progression. The factor column data must not be repeated. For example, sorting 0~100 can be sorted in one step. The number of exchanges is: , the calculation time complexity is: , and the worst space complexity is . If the characteristics of the series meet the conditional requirements of this sorting method: "The array is a continuous integer or an arithmetical progression that does not repeat", the in-place interpolation tag sort will be an excellent sorting method that is extremely fast and saves memory space. In-place Interpolation Tag Sort Algorithm In-place Interpolation Tag Sort sorts non-repeating consecutive integer series, only one Boolean data type tag array with the same length as the original array, the array calculates the interpolation of the data from the beginning, and the interpolation points to a new position of the array. Position, the position that has been swapped is marked as true in the corresponding position of the tag array, and is incremented until the end of the array is sorted. Algorithm process: Set an equal number of tag arrays to initialize to false values. Visit the array when tag[i] is false, calculate the position corresponding to the interpolation=p. Swap a[i] and a[p], let tag[p] = true. The tour array is completed and the sorting is completed. Practice JavaScript code: Array.prototype.InPlaceTagSort = function() { // Edit Date: 2019-07-02 var n = this.length; var Tag = new Array(n); for (i = 0; i < n; i++) { Tag[i] = false; } var min = this[0]; var max = this[0]; for (i = 1; i < n; i++) { if (this[i] < min) { min = this[i]; } else { if (this[i] > max) { max = this[i]; } } } var p = 0; var temp = 0; for (i = 0; i < n; i++) { while (Tag[i] == false) { p = Math.floor(((this[i] - min) / (max - min)) * (n - 1)); temp = this[i]; this[i] = this[p];