this[p] = temp; Tag[p] = true; } } }; needSortArray.InPlaceTagSort(); The origin of In-place sorting performed in time In "Mathematical Analysis of Algorithms", (Information Processing '71, North Holland Publ.'72) Donald Knuth remarked "... that research on computional complexity is an interesting way to sharpen our tools for more routine problems we face from day to day." The famous American computer scientist Donald Knuth in the mathematical analysis of algorithms pointed out that:"With respect to the sorting problem, Knuth points out, that 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 time if we would be allowed to manipulate n extra "tag" bits specifying how much of the permutation has been carried out at any time. Without such tag bits, he concludes "it seems reasonable to conjecture that every algorithm will require for in-situ permutation at least steps on the average." The In-place Interpolation Tag Sort is one of the sorting algorithms that the Donald Knuth professor said: "manipulate n extra "tag" bits...finding the cycle leaders, and in-situ permutations could easily be performed in time". Similar sorting method Flashsort Proxmap sort American flag sort Bucket sort mixing other sorting methods and recursive algorithm Bucket sort can be mixed with other sorting methods to complete sorting. If it is sorted by bucket sort and insert sort, also is a fairly efficient sorting method. But when the series appears a large deviation from the value: For example, when the maximum value of the series is greater than N times the next largest value. After the series of columns are processed, the distribution is that all the elements except the maximum value fall into the same bucket. The second sorting method uses insert sort. May cause execution complexity to fall into . This has lost the meaning and high-speed performance of using bucket sort. Interpolation sort is a way of recursively using bucket sort. After performing recursion, still use bucket sort to disperse the series. This can avoid the above situation. If you want to make the recursive interpolation sort execution complexity fall into , it is necessary to present a factorial amplification in the entire series. In fact, there is very little chance that a series of special distributions will occur. References External links interpolationSort.html histogramSort.html The FlashSort Algorithm Mathematical Analysis of Algorithms http://www.drdobbs.com/database/the-flashsort1-algorithm/184410496 桶排序遞迴方式演算法 Bucket sort Recursive method.