= function() {//-- Edit date:2019/11/14 --// var end = this.length; var sortedArray = new Array(end); var interpolation = new Array(end); var hitCount = new Array(end); var divideSize = new Array(); divideSize[0] = end; while (divideSize.length > 0) { distribute(this); } // Repeat function distribute to Array function distribute(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 { for (var i = start; i < end; i++) { hitCount[i] = 0; } for (var i = start; i < end; i++) { interpolation[i] = start + Math.floor(((A[i] - min ) / (max - min ) ) * (size - 1 )); hitCount[interpolation[i]]++; } for (var i = start; i < end; i++) { if (hitCount[i] > 0) { divideSize.push(hitCount[i]); } } hitCount[end-1] = end - hitCount[end-1]; for (var i = end-1; i > start; i--) { hitCount[i-1] = hitCount[i] - hitCount[i-1]; } for (var i = start; i < end; i++) { sortedArray[hitCount[interpolation[i]]] = A[i]; hitCount[interpolation[i]]++; } for (var i = start; i < end; i++) { A[i] = sortedArray[i]; } } } }; Variant Interpolation tag sort Interpolation Tag Sort is a variant of Interpolation Sort. Applying the bucket sorting and dividing method, the array data is distributed into a limited number of buckets by mathematical interpolation formula, and the bucket then recursively the original processing program until the sorting is completed. Interpolation tag sort is a recursive sorting method for interpolation sorting. To avoid stacking overflow caused by recursion, the memory crashes. Instead, use a Boolean data type tag array to operate the recursive function to release the memory. The extra memory space required is close to . Contains a two-dimensional array of dynamically allocated memory and a Boolean data type tag array. Stack, queue, associative array, and tree structure can be implemented as buckets. As the JavaScript array object is suitable for this sorting method, the difference in data structure is related to the speed of data access and thus the time required for sorting. The linear time Θ(n) is used when the values in the array to be sorted are