Interpolation sort is a sorting algorithm that 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

Class	Sorting Algorithm
Data structure	Array
Worst-case performance	${\displaystyle O(n^{2})}$
Best-case performance	${\displaystyle O(n)}$
Average performance	${\displaystyle O(n+k)}$
Worst-case space complexity	${\displaystyle O(n*3)}$
Optimal	${\displaystyle O(n)}$

Interpolation sort (or histogram sort).^[1] 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.^[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 ${\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 the array. 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)}$.^[3] 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 ${\displaystyle O(n)}$.^[4]

Interpolation sort algorithm

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 and sorted is completed. Execute [Divide function] if it is not cleared.
3. [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.
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].

Histogram sort algorithm

The NIST definition: An efficient 3-pass refinement of a bucket sort algorithm.^[5]

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.

Practice

Interpolation sort implementation

JavaScript code:

Array.prototype.interpolationSort = function()
{
  var divideSize = new Array();
  var end = this.length;
  divideSize[0] = end;
  while (divideSize.length > 0) { divide(this); } 
  // Repeat function divide to ArrayList
  function divide(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 {
      var p = 0;
      var bucket = new Array(size);
      for (var i = 0; i < size; i++) { bucket[i] = new Array(); }
      for (var i = start; i < end; i++) {
        p = Math.floor(((A[i] - min ) / (max - min ) ) * (size - 1 ));
        bucket[p].push(A[i]);
      }
      for (var i = 0; i < size; i++) {
        if (bucket[i].length > 0) {
          for (var j = 0; j < bucket[i].length; j++) { A[start++] = bucket[i][j]; }
          divideSize.push(bucket[i].length);
        }
      }
    }
  }
};

Interpolation sort recursive method

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

Array.prototype.interpolationSort= function()
{//-- Edit date:2019/08/31 --//
  var start = 0;
  var size = this.length;
  var min = this[0];
  var max = this[0]; 
  for (var i = 1; i < size; i++) {
    if (this[i] < min) { min = this[i]; }
    else {if (this[i] > max) { max = this[i];} }
  }
  if (min != max) {
    var bucket = new Array(size);
    for (var i = 0; i < size; i++) { bucket[i] = new Array(); }
    var interpolation = 0;
    for (var i = 0; i < size; i++) {
      interpolation = Math.floor(((this[i] - min) / (max - min)) * (size - 1));
      bucket[interpolation].push(this[i]);
    }
    for (var i = 0; i < size; i++) {
      if (bucket[i].length > 1) { bucket[i].interpolationSort(); } // Recursion
      for (var j = 0; j < bucket[i].length; j++) { this[start++] = bucket[i][j]; }
    }
  }
};

Histogram sort implementation

Array.prototype.histogramSort = 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

Class	Sorting Algorithm
Data structure	Array
Worst-case performance	${\displaystyle O(n^{2})}$
Best-case performance	${\displaystyle O(n)}$
Average performance	${\displaystyle O(n+k)}$
Worst-case space complexity	${\displaystyle O(2n+(n)bits)}$
Optimal	${\displaystyle O(n)}$

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 ${\displaystyle 2n+(n)bits}$. 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 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)}$.^[3]

Interpolation tag sort algorithm

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].

Practice

JavaScript code:

Array.prototype.InterpolaionTagSort = function()
{// Whale Chen agrees to "Wikipedia CC BY-SA 3.0 License". Sign date: 2019-06-21 //
  var end = this.length; 
  if (end > 1) { 
    var start = 0 ; 
    var Tag = new Array(end);          // Algorithm step-1 
    for (var i = 0; i < end; i++) { Tag[i] = false; } 
    Divide(this); 
  } 
  while (end > 1) {                     // Algorithm step-2  
    while (Tag[--start] == false) { } // Find the next bucket's start
    Divide(this); 
  }

  function Divide(A) {   
    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 = start; }    // Algorithm step-3 Start to be the next bucket's end
    else {                                          
      var interpolation = 0; 
      var size = end - start; 
      var Bucket = new Array( size );    // Algorithm step-4         
      for (var i = 0; i < size; i++) { Bucket[i] = new Array(); }  
      for (var i = start; i < end; i++) {  
         interpolation = Math.floor (((A[i] - min) / (max - min)) * (size - 1));
         Bucket[interpolation].push(A[i]); 
      } 
      for (var i = 0; i < size; i++) {
        if (Bucket[i].length > 0) {    // Algorithm step-5      
          Tag[start] = true; 
          for (var j = 0; j < Bucket[i].length; j++) { A[start++] = Bucket[i][j]; } 
        } 
      }  
    }
  } // Algorithm step-6 
};

In-place Interpolation Tag Sort

In-Place Interpolation Tag Sort

Class	Sorting Algorithm
Data structure	Array
Worst-case performance	${\displaystyle O(n)}$
Best-case performance	${\displaystyle O(n)}$
Average performance	${\displaystyle O(n)}$
Worst-case space complexity	${\displaystyle O(n)bits}$
Optimal	${\displaystyle O(n)}$

The in-place interpolation tag sort is an in-place algorithm of interpolation sort. 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.

The factor column data must not be repeated. For example, sorting 0~100 can be sorted in one step. 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}$. 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.

In-place Interpolation Tag Sort Algorithm

In-place Interpolation Tag Sort sorts non-repeating consecutive integer series, only one Boolean data type tag array with the same length as the original array, the array calculates the interpolation of the data from the beginning, and the interpolation points to a new position of the array. Position, the position that has been swapped is marked as true in the corresponding position of the tag array, and is incremented until the end of 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.

Practice

JavaScript code:

Array.prototype.InPlaceTagSort = function()
{ // Edit Date: 2019-07-02
  var n = this.length;
  var Tag = new Array(n);
  for (i = 0; i < n; i++) { Tag[i] = false; }
  var min = this[0];
  var max = this[0];
  for (i = 1; i < n; i++) { if (this[i] < min) { min = this[i]; }
  else { if (this[i] > max) { max = this[i]; } } } 
  var p = 0;
  var temp = 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();

The origin of In-place sorting performed in ${\displaystyle O(n)}$ time

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 ${\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."^[6]

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".

Similar sorting method

1. Flashsort
2. Proxmap sort
3. 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 ${\displaystyle O(n^{2})}$. 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 ${\displaystyle O(n^{2})}$, 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.