Estimated distribution counting – most often reinvented sorting

import java.util.Arrays;
import java.util.Date;
import java.util.Random;

public class HashSort {

 // The size of the source data array
 static int SOURCELEN = 1000000;
 int source[] = new int[SOURCELEN];
 
 // Copy of source data for comparison with quick sort
 int quick[] = new int[SOURCELEN];
 
 // Block size for hash sorting
 static int SORTBLOCK = 500;
 static int k = 3;
 
 // Temporary array
 static int TMPLEN = (SOURCELEN <SORTBLOCK * k)? SORTBLOCK * k: SOURCELEN;
 int tmp[] = new int[TMPLEN];
 
 // Range of values ​​of the source data
 static int MIN_VAL = 10;
 static int MAX_VAL = 1000000;

 int minValue = 0;
 int maxValue = 0;
 double hashKoef = 0;
 
 // Fill the source data array with random values
 public void randomize () {
  int i;
  Random rnd = new Random ();
  for (i = 0; i <SOURCELEN; i ++) {
   int rndValue = MIN_VAL + ((int) (rnd.nextDouble () * ((double) MAX_VAL-MIN_VAL)));
   source[i] = rndValue;
  }
 }

 // Search for the minimum and maximum values ​​plus the calculation of the coefficient for the hash function
 public void findMinMax (int startIndex, int endIndex) {
  int i;
  minValue = source[startIndex];
  maxValue = source[startIndex];
  for (i = startIndex + 1; i<=endIndex; i++) {
   if( source[i] > maxValue) {
    maxValue = source[i];
   }
   if (source[i] <minValue) {
    minValue = source[i];
   }
  }
  hashKoef = ((double) (k-1) * 0.9) * ((double) (endIndex-startIndex) / ((double) maxValue- (double) minValue));
 }
 
 // Gluing (in other words, merging) two adjacent sorted parts of the array
 public void stickParts (int startIndex, int mediana, int endIndex) {
  int i = startIndex;
  int j = mediana + 1;
  int k = 0;
  // As long as there are elements in both subarrays - merge them
  while (i <= mediana && j <= endIndex) {
   if (source[i]mediana) {
   while (j<=endIndex) {
    tmp[k] = source[j];
    j++;
    k++;
   }
  }
  //Если в правом остались элементы - переносим в конец общего подмассива
  if(j>endIndex) {
   while (i <= mediana) {
    tmp[k] = source[i];
    i ++;
    k ++;
   }
  }
  
  System.arraycopy (tmp, 0, source, startIndex, endIndex-startIndex + 1);
 }
 
 // Shift right in the temporary array to resolve collisions
 // Move several consecutive elements to free the cell to the left
 boolean shiftRight (int index) {
  int endpos = index;
  while (tmp[endpos] ! = 0) {
   endpos ++;
   if (endpos == TMPLEN) return false;
  }
  
  while (endpos! = index) {
   tmp[endpos] = tmp[endpos-1];
   endpos--;
  }
      
  tmp[endpos] = 0;
  
  return true;
 }

 // Hash function for sorting by hashing
 public int hash (int value) {
  return (int) (((double) value - (double) minValue) * hashKoef);
 }
 
 // Insert values ​​into a temporary array with collision resolution
 public void insertValue (int index, int value) {
  int _index = index;
  // If the place is taken, then look to the right
  // move while the cells are busy and the inserted element is larger than those already in the hash array
  while (tmp[_index] ! = 0 && tmp[_index] <= value) {_index ++; }
  // If still busy and reached the item that is larger than the inserted
  if (tmp[_index] ! = 0) {
   shiftRight (_index); // Shift consecutive larger elements to the right
  }
  tmp[_index] = value; // Place freely - insert an element
 }
 
 // Copy the sorted data from the temporary array to the original
 public void extract (int startIndex, int endIndex) {
  int j = startIndex;
  for (int i = 0; i <(SORTBLOCK * k); i ++) {
   if (tmp[i] ! = 0) {
    source[j] = tmp[i];
    j ++;
   }
  }
 }
 
 // Clear the temporary array
 public void clearTMP () {
  if (tmp.length <SORTBLOCK * k) {
   Arrays.fill (tmp, 0);
  } else {
   Arrays.fill (tmp, 0, SORTBLOCK * k, 0);
  }
 }
 
 // Hash Sort
 public void hashingSort (int startIndex, int endIndex) {
  
  //one. Finding the minimum and maximum values ​​with the calculation of the hashing coefficient
  findMinMax (startIndex, endIndex);
  
  // 2. Clearing a temporary array
  clearTMP ();
  
  // 3. Insert into a temporary array using a hash function
  for (int i = startIndex; i <= endIndex; i ++) {
   insertValue (hash (source[i]), source[i]);
  }
  
  //4. Moving sorted data from a temporary array to the original
  extract (startIndex, endIndex);
 }
 
 // Recursive descent with a dichotomy to the level of a hash sorting block
 public void sortPart (int startIndex, int endIndex) {

  // If the size of the subarray is less than 500, then we directly sort the hash
  if ((endIndex - startIndex) <= SORTBLOCK ) {
     hashingSort(startIndex, endIndex);
     return;
  }
  
  //Если размер > 500 then divide in half and recursion to each half
  int mediana = startIndex + (endIndex - startIndex) / 2;
  sortPart (startIndex, mediana); // Recursion To The Left Half
  sortPart (mediana + 1, endIndex); // Recursion to the right half
  stickParts (startIndex, mediana, endIndex); // Halves are recursively sorted - glue them
 }
 
 // Sort the entire array as the maximum possible subarray
 public void sort () {
  sortPart (0, SOURCELEN-1);
 }
 
 public static void main (String[] args) {
  HashSort hs = new HashSort ();
  hs.randomize ();
  hs.sort ();
 }

}

The formula itself is called a hash function, and the auxiliary array for approximate distribution is called a hash table.

References

Interpolation & Histogram, Flash, Proxmap

Solomon, Hash Table, Flash

Series Articles:

• Excel application AlgoLab.xlsm
• Exchange Sorts
• Insertion Sorts
• Sort by selection
• Merge Sorts
• Sort by distribution
  • Counting sorts with approximate distribution
  • American Flag Sort
  • Suffix tree in bitwise sorting
  • Comparing Distribution Sorts

Approximation sorting appeared in the AlgoLab Excel application (in this case, in the initial unsorted array, the random fractional part is appended to the integers). Solomon and Flash have been there for a long time, but have not yet implemented interpolation, hash, and a histogram.