evenly distributed. The bucket sort algorithm does not limit the sorting to the lower limit of . Interpolation tag sort average performance complexity is . Interpolation tag sort algorithm Set a tag array equal to the original array size and initialize to a false value. [Main Sort] Determines whether all buckets of the original array have been sorted. If the sorting is not completed, the [Divide function] is executed. [Divide function] Find the maximum and minimum values in the bucket. If the maximum value is equal to the minimum value, the sorting is completed and the division is stopped. Set up a two-dimensional array as all the empty buckets. Divide into the bucket according to the interpolation number. After dividing into the bucket, mark the starting position of the bucket as a true value in the tag array. And put the items back into the original array one by one from all the buckets that are not empty. Return to [Main Sort]. Practice JavaScript code: Array.prototype.InterpolaionTagSort = function() {// Whale Chen agrees to "Wikipedia CC BY-SA 3.0 License". Sign date: 2019-06-21 // var end = this.length; if (end > 1) { var start = 0 ; var Tag = new Array(end); // Algorithm step-1 for (var i = 0; i < end; i++) { Tag[i] = false; } Divide(this); } while (end > 1) { // Algorithm step-2 while (Tag[--start] == false) { } // Find the next bucket's start Divide(this); } function Divide(A) { 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 = start; } // Algorithm step-3 Start to be the next bucket's end else { var interpolation = 0; var size = end - start; var Bucket = new Array( size ); // Algorithm step-4 for (var i = 0; i < size; i++) { Bucket[i] = new Array(); } for (var i = start; i < end; i++) { interpolation = Math.floor (((A[i] - min) / (max - min)) * (size - 1)); Bucket[interpolation].push(A[i]); } for (var i = 0; i < size; i++) { if (Bucket[i].length > 0) { // Algorithm step-5 Tag[start] = true; for (var j = 0; j < Bucket[i].length; j++)