[1] It is a sorting algorithm that uses the interpolation formula to disperse data divide and conquer.
[2] 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
However the execution complexity can still be maintained as an efficient sorting method of
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
[4] The NIST definition: An efficient 3-pass refinement of a bucket sort algorithm.
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.
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 evenly distributed.
Interpolation tag sort average performance complexity is
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.
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.
Algorithm process: JavaScript code: In "Mathematical Analysis of Algorithms", Donald Knuth remarked "... that research on computational complexity is an interesting way to sharpen our tools for more routine problems we face from day to day.
"[6] Knuth further pointed out that, with respect to the sorting problem, time effective in-situ permutation is inherently connected with the problem of finding the cycle leaders, and in-situ permutations could easily be performed in
Without such tag bits, he concludes "it seems reasonable to conjecture that every algorithm will require for in-situ permutation at least
extra "tag" bits...finding the cycle leaders, and in-situ permutations could easily be performed in
After the series of columns are processed, the distribution is that all the elements except the maximum value fall into the same bucket.
This has lost the meaning and high-speed performance of using bucket sort.
After performing recursion, still use bucket sort to disperse the series.
If you want to make the recursive interpolation sort execution complexity fall into
In fact, there is very little chance that a series of special distributions will occur.