This articleneeds additional citations forverification. Please helpimprove this article byadding citations to reliable sources. Unsourced material may be challenged and removed. Find sources: "Interpolation sort" – news ·newspapers ·books ·scholar ·JSTOR(January 2026) (Learn how and when to remove this message)

Interpolation sort (or histogram sort) is asorting algorithm that uses aninterpolation formula todivide and conquer.^[1] It is a variant ofbucket sort. Data is assigned to buckets using an interpolation function:$${\displaystyle \text{Interpolation}(x)=\lfloor \frac{x-\text{min}}{\text{max}-\text{min}}\times (\text{ArraySize}-1)\rfloor }$$where${\displaystyle \text{min}}$ and${\displaystyle \text{max}}$ are the minimum and maximum values within the array, and thefloor function is used. This function returns an array index to where element${\displaystyle x}$ can be repositioned.

Interpolation sort

Class	Sorting Algorithm
Data structure	Array
Worst-caseperformance	${\displaystyle O(n^2)}$
Best-caseperformance	${\displaystyle O(n)}$
Averageperformance	${\displaystyle O(n+k)}$
Worst-casespace complexity	${\displaystyle O(n\ast 3)}$
Optimal	${\displaystyle O(n)}$

This sectionmay beconfusing or unclear to readers. In particular, too much technical jargon with no basic explanations. Please helpclarify the section. There might be a discussion about this onthe talk page.(January 2026) (Learn how and when to remove this message)

Interpolation sort uses an array of record bucket lengths corresponding to the original number column. The array prevents the space complexity from becoming${\displaystyle O(n^2)}$ due to memory stacking. The segmentation record of the length array can using secondary function dynamically declare and delete the memory space of thearray. The space complexity required to control the recursive program is${\displaystyle O(3n)}$. 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${\displaystyle O(n+k)}$.

Thearray of dynamically allocated memory can be implemented using an array object (such as inJavaScript) or more basically via alinked list,stack,queue,associative array, ortree structure. The type ofdata structure affects the speed of data access and thus the sorting time. When the values in the ordered array are uniformly distributed in anarithmetic progression, theorder of interpolation sort is linear time,${\displaystyle O(n)}$.

1. Set a bucket length array to record the length of the unsorted bucket. Initialize into the original array length.
2. [Main Sort] If the bucket length array is cleared, the sort is completed. Otherwise execute Divide function.
3. [Divide function]Pop the bucket at 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 bucket is sorted, so stop Divide.
4. Set up a two-dimensional array as all empty buckets. Divide into the bucket according to the interpolation number.
5. 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.
6. Return to [Main Sort].

NIST describes the histogram sort as an efficient 3-pass refinement of a bucket sort algorithm.^[2]

1. The first pass counts the number of items for each bucket in an auxiliary array, and then makes a running total so each auxiliary entry is the number of preceding items.
2. The second pass puts each item in its proper bucket according to the auxiliary entry for the key of that item.
3. The last pass sorts each bucket.

JavaScript code:

Array.prototype.interpolationSort=function(){vardivideSize=newArray();varend=this.length;divideSize[0]=end;while(divideSize.length>0){divide(this);}// Repeat function divide to ArrayListfunctiondivide(A){varsize=divideSize.pop();varstart=end-size;varmin=A[start];varmax=A[start];for(vari=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{varp=0;varbucket=newArray(size);for(vari=0;i<size;i++){bucket[i]=newArray();}for(vari=start;i<end;i++){p=Math.floor(((A[i]-min)/(max-min))*(size-1));bucket[p].push(A[i]);}for(vari=0;i<size;i++){if(bucket[i].length>0){for(varj=0;j<bucket[i].length;j++){A[start++]=bucket[i][j];}divideSize.push(bucket[i].length);}}}}};

Worst-case space complexity:${\displaystyle O(n^2)}$

Array.prototype.interpolationSort=function(){//-- Edit date:2019/08/31 --//varstart=0;varsize=this.length;varmin=this[0];varmax=this[0];for(vari=1;i<size;i++){if(this[i]<min){min=this[i];}else{if(this[i]>max){max=this[i];}}}if(min!=max){varbucket=newArray(size);for(vari=0;i<size;i++){bucket[i]=newArray();}varinterpolation=0;for(vari=0;i<size;i++){interpolation=Math.floor(((this[i]-min)/(max-min))*(size-1));bucket[interpolation].push(this[i]);}for(vari=0;i<size;i++){if(bucket[i].length>1){bucket[i].interpolationSort();}// Recursionfor(varj=0;j<bucket[i].length;j++){this[start++]=bucket[i][j];}}}};

Array.prototype.histogramSort=function(){//-- Edit date:2019/11/14 --//varend=this.length;varsortedArray=newArray(end);varinterpolation=newArray(end);varhitCount=newArray(end);vardivideSize=newArray();divideSize[0]=end;while(divideSize.length>0){distribute(this);}// Repeat function distribute to Arrayfunctiondistribute(A){varsize=divideSize.pop();varstart=end-size;varmin=A[start];varmax=A[start];for(vari=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(vari=start;i<end;i++){hitCount[i]=0;}for(vari=start;i<end;i++){interpolation[i]=start+Math.floor(((A[i]-min)/(max-min))*(size-1));hitCount[interpolation[i]]++;}for(vari=start;i<end;i++){if(hitCount[i]>0){divideSize.push(hitCount[i]);}}hitCount[end-1]=end-hitCount[end-1];for(vari=end-1;i>start;i--){hitCount[i-1]=hitCount[i]-hitCount[i-1];}for(vari=start;i<end;i++){sortedArray[hitCount[interpolation[i]]]=A[i];hitCount[interpolation[i]]++;}for(vari=start;i<end;i++){A[i]=sortedArray[i];}}}};

Interpolation tag sort

Class	Sorting Algorithm
Data structure	Array
Worst-caseperformance	${\displaystyle O(n^2)}$
Best-caseperformance	${\displaystyle O(n)}$
Averageperformance	${\displaystyle O(n+k)}$
Worst-casespace complexity	${\displaystyle O(2n+(n)bits)}$
Optimal	${\displaystyle O(n)}$

Interpolation tag sort is arecursive variant of interpolation sort. After the array data is distributed into buckets via an interpolation function, each bucket recursively runs the original algorithm until the sorting is completed.

To avoidstack overflow caused by recursion, use a Boolean data type tag array to operate the recursive function to release the memory. The extra memory space required is close to${\displaystyle 2n+(n)}$ bits. Contains a two-dimensional array of dynamically allocated memory and a Boolean data type tag array. Buckets can be implemented using a stack, queue, associative array, or tree structure.

Like interpolation sort, interpolation tag sort runs in linear time${\displaystyle O(n)}$ when the values in the array to be sorted are evenly distributed. The bucket sort algorithm does not limit the sorting to the lower limit of${\displaystyle O(nlogn)}$. Interpolation tag sort average performance complexity is${\displaystyle O(n+k)}$.

1. Set a tag array equal to the original array size and initialize to a false value.
2. [Main Sort] Determines whether all buckets of the original array have been sorted. If the sorting is not completed, the [Divide function] is executed.
3. [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.
4. Set up a two-dimensional array as all the empty buckets. Divide into the bucket according to the interpolation number.
5. 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.
6. Return to [Main Sort].

JavaScript code:

Array.prototype.InterpolaionTagSort=function(){// Whale Chen agrees to "Wikipedia CC BY-SA 3.0 License". Sign date: 2019-06-21 //varend=this.length;if(end>1){varstart=0;varTag=newArray(end);// Algorithm step-1for(vari=0;i<end;i++){Tag[i]=false;}Divide(this);}while(end>1){// Algorithm step-2while(Tag[--start]==false){}// Find the next bucket's startDivide(this);}functionDivide(A){varmin=A[start];varmax=A[start];for(vari=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 endelse{varinterpolation=0;varsize=end-start;varBucket=newArray(size);// Algorithm step-4for(vari=0;i<size;i++){Bucket[i]=newArray();}for(vari=start;i<end;i++){interpolation=Math.floor(((A[i]-min)/(max-min))*(size-1));Bucket[interpolation].push(A[i]);}for(vari=0;i<size;i++){if(Bucket[i].length>0){// Algorithm step-5Tag[start]=true;for(varj=0;j<Bucket[i].length;j++){A[start++]=Bucket[i][j];}}}}}// Algorithm step-6};

In-place interpolation tag sort

Class	Sorting Algorithm
Data structure	Array
Worst-caseperformance	${\displaystyle O(n)}$
Best-caseperformance	${\displaystyle O(n)}$
Averageperformance	${\displaystyle O(n)}$
Worst-casespace complexity	${\displaystyle O(n)bits}$
Optimal	${\displaystyle O(n)}$

In-place interpolation tag sort is anin-place algorithm variant of interpolation sort. It sorts non-repeating consecutive integer series. It can achieve sorting by only N times of swapping by maintaining N bit tags, saving time and memory space. However, the array to be sorted must be either a continuous integer sequence or a non-repeating arithmetical progression.

The factor column data must not be repeated. For example, sorting 0~100 can be sorted in one pass. The number of exchanges is:${\displaystyle O(n)}$, the calculation time complexity is:${\displaystyle O(n)}$, and the worst space complexity is${\displaystyle O(n)}$ bits.

This algorithm only uses one additional tag array. This tag array has the same length as the original array and is of Boolean data type. For each unswapped element, the algorithm calculates a new interpolated positionp and swaps the two elements in the array. The tag array is marked true at positionp, and the algorithm is incremented until it reaches the last element, at which point the array is sorted.

Algorithm process:

1. Set an equal number of tag arrays to initialize to false values.
2. Visit the array when tag[i] is false, calculate the position corresponding to the interpolation=p.
3. Swap a[i] and a[p], let tag[p] = true.
4. The tour array is completed and the sorting is completed.

JavaScript code:

Array.prototype.InPlaceTagSort=function(){// Edit Date: 2019-07-02varn=this.length;varTag=newArray(n);for(i=0;i<n;i++){Tag[i]=false;}varmin=this[0];varmax=this[0];for(i=1;i<n;i++){if(this[i]<min){min=this[i];}else{if(this[i]>max){max=this[i];}}}varp=0;vartemp=0;for(i=0;i<n;i++){while(Tag[i]==false){p=Math.floor(((this[i]-min)/(max-min))*(n-1));temp=this[i];this[i]=this[p];this[p]=temp;Tag[p]=true;}}};needSortArray.InPlaceTagSort();

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."^[3]

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${\displaystyle O(n)}$ time if we would be allowed to manipulate${\displaystyle 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${\displaystyle n\log n}$ steps on the average."^[3]

The in-place interpolation tag sort is one of the sorting algorithms that prof. Donald Knuth said: "manipulate${\displaystyle n}$ extra "tag" bits...finding the cycle leaders, and in-situ permutations could easily be performed in${\displaystyle O(n)}$ time".

Bucket sort is limited in some situations. For example, consider a case where the maximum data value is greater than N times the next largest value. After processing, all elements except the maximum value fall into the same bucket; a poor distribution. The second sorting pass using e.g.insert sort may cause execution complexity to fall into${\displaystyle O(n^2)}$. This loses the benefits 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${\displaystyle O(n^2)}$, it is necessary to present afactorial amplification in the entire series.^{[clarification needed]} In fact, there is very little chance that a series of special distributions will occur.

• Flashsort
• Proxmap sort
• American flag sort

• interpolationSort.html
• histogramSort.html
• The FlashSort Algorithm
• Mathematical Analysis of Algorithms
• http://www.drdobbs.com/database/the-flashsort1-algorithm/184410496
• 桶排序遞迴方式演算法 Bucket sort Recursive method. Whale Chen 2012/09/16
• 插值標簽排序演算法 Interpolation Tag Sort Algorithm. Whale Chen 2013/03/24
• interpolation sort (Pascal version available)
• w3schools JavaScript Array Sort testing platform

• Sorting algorithms
• Stable sorts

• Articles with short description
• Short description matches Wikidata
• Articles needing additional references from January 2026
• All articles needing additional references
• Wikipedia articles needing clarification from January 2026
• All Wikipedia articles needing clarification