Interpolation sort is a kind of bucket sort. It uses an interpolation formula to assign data to the bucket. A general interpolation formula is: Interpolation = INT(((Array[i] - min) / (max - min)) * (ArraySize - 1)) Algorithm Interpolation sort (or histogram sort). It is a sorting algorithm that uses the interpolation formula to disperse data divide and conquer. Interpolation sort is also a variant of bucket sort algorithm. The interpolation sort method uses an array of record bucket lengths corresponding to the original number column. By operating the maintenance length array, the recursive algorithm can be prevented from changing the space complexity to due to memory stacking. The segmentation record of the length array can using secondary function dynamically declare and delete the memory space of the array. The space complexity required to control the recursive program is . Contains a two-dimensional array of dynamically allocated memories and an array of record lengths. However the execution complexity can still be maintained as an efficient sorting method of . Array of dynamically allocated memory can be implemented by linked list, stack, queue, associative array, tree structure, etc. An array object such as JavaScript is applicable. The difference in data structure is related to the speed of data access and thus the time required for sorting.When the values in the ordered array are uniformly distributed approximately the arithmetic progression, the linear time of interpolation sort ordering is . Interpolation sort algorithm Set a bucket length array to record the length of the unsorted bucket. Initialize into the original array length. [Main Sort] If the bucket length array is cleared and sorted is completed. Execute [Divide function] if it is not cleared. [Divide function] Execute Divide by pop a bucket length from the end of the bucket length array. Find the maximum and minimum values in the bucket. If the maximum value is equal to the minimum value, the sorting is completed to stop Divide. Set up a two-dimensional array as all empty buckets. Divide into the bucket according to the interpolation number. After dividing into the buckets, push the length of the buckets into the array of bucket length. And put the items back into the original array one by one from all the buckets that are not empty. Return to [Main Sort]. Histogram sort algorithm The NIST definition: An efficient 3-pass refinement of a bucket sort algorithm. The first pass