Array.prototype.interpolationSort = function() {
 
 var divideSize = new Array();
 var end = this.length;
 divideSize[0] = end;
 
 while(divideSize.length > 0) {divide(this);}

 function divide(A) {
  
  var size = divideSize.pop();
  var start = end - size;
  var min = A[start];
  var max = A[start];
  var temp = 0;
  
  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);
    }
   }
  }
 }
};

Array.prototype.bucketSort = function() {
 
 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].bucketSort();} //Recursion
   for(var j = 0; j < bucket[i].length; j++) {this[start++] = bucket[i][j];}
  }
  
 }
};

Array.prototype.histogramSort = function() {
 
 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);}
 
 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];}

  }
 }
};

Array.prototype.InterpolaionTagSort = function() {

 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); 
 }
 
 //Algorithm step-2
 while(end > 1) {
  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;
   
  } else {
   
   //Algorithm step-3 Start to be the next bucket's end                                         
   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 
};

Array.prototype.InPlaceTagSort = function() {

 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;
  } 
 } 
};

/**
 * FlashSort.java - integer version 
 * Translation of Karl-Dietrich Neubert's algorithm into Java by   
 * Rosanne Zhang
 */
   
class FlashSort {

 static int   n;
 static int   m;
 static int[] a;
 static int[] l;
    
 /* constructor 
 @param size of the array to be sorted */
 public static void flashSort(int size) {

  n = size;
  generateRandomArray();

  long start = System.currentTimeMillis();
  partialFlashSort();
  long mid = System.currentTimeMillis();
  insertionSort();
  long end = System.currentTimeMillis();

  // print the time result
  System.out.println("Partial flash sort time     : " + (mid - start));
  System.out.println("Straight insertion sort time: " + (end - mid));
 }

 /* Entry point */
 public static void main(String[] args) {
  
  int size = 0;

  if (args.length == 0) {
   usage();
   System.exit(1);
  }

  try {
   size = Integer.parseInt(args[0]); 
  }

  catch (NumberFormatException nfe) {
   usage();
   System.exit(1);
  }

  FlashSort.flashSort(size);
 }

 /* Print usage */

 private static void usage() {
  System.out.println();
  System.out.println("Usage: java FlashSort n ");
  System.out.println("       n is size of array to sort");
 }

 /* Generate the random array */
 private static void generateRandomArray() {
  
  a = new int[n];
  for(int i=0; i < n; i++) {
   a[i] = (int)(Math.random() * 5 * n);
  }

  m = n / 20;

  l = new int[m];   
 }

 /* Partial flash sort */

 private static void partialFlashSort() {

  int i = 0, j = 0, k = 0;
  int anmin = a[0];
  int nmax  = 0;

  for(i=1; i < n; i++) {
   if (a[i] < anmin) anmin=a[i];
   if (a[i] > a[nmax]) nmax=i;            
  }

  if(anmin == a[nmax]) return;

  double c1 = ((double)m - 1) / (a[nmax] - anmin);

  for(i=0; i < n; i++) {
   k= (int) (c1 * (a[i] - anmin));
   l[k]++;
  }

  for(k=1; k < m; k++) {
   l[k] += l[k - 1];
  }

  int hold = a[nmax];
  a[nmax] = a[0];
  a[0] = hold;

  int nmove = 0;
  int flash;
  j = 0;
  k = m - 1;

  while(nmove < n - 1) {
   
   while(j > (l[k] - 1)) {
    j++;
    k = (int) (c1 * (a[j] - anmin));
   }

   flash = a[j];

   while(!(j == l[k])) {
	   
    k = (int) (c1 * (flash - anmin));

    hold = a[l[k] - 1];
    a[l[k] - 1] = flash;
    flash = hold;

    l[k]--;
    nmove++;

   }
  }
 }

 /* Straight insertion sort */
 private static void insertionSort() {

  int i, j, hold;

  for(i = a.length - 3; i >= 0; i--) {

   if(a[i + 1] < a[i]) {
    
	hold = a[i];
    j = i;

    while (a[j + 1] < hold) {
     a[j] = a[j + 1];
     j++;
    }

    a[j] = hold;
   }
  }
 }

 /* For checking sorting result and the distribution */
 private static void printArray(int[] ary) {
  
  for(int i=0; i < ary.length; i++) {
   
   if((i + 1) % 10 ==0) {
    System.out.println(ary[i]);
   } else {
    System.out.print(ary[i] + " ");
   }
   
   System.out.println();
  }
 }
}

Array.prototype.ProxmapSort = function() {
	
 var start = 0;
 var end = this.length;
 var A2 = new Array(end);
 var MapKey = new Array(end);
 var hitCount = new Array(end);
  
 for(var i = start; i < end; i++) {hitCount[i] = 0;}
  
 var min = this[start];
 var max = this[start];
 for (var i = start+1; i < end; i++){
  if (this[i] < min) {
	  min = this[i];
  } else {
   if(this[i] > max) {max = this[i];}
  }
 }
 
 //Optimization 1.Save the MapKey[i].
 for (var i = start; i < end; i++) {
  MapKey[i] = Math.floor(((this[i] - min ) / (max - min)) * (end - 1));
  hitCount[MapKey[i]]++;
 }

 //Optimization 2.ProxMaps store in the hitCount.
 hitCount[end-1] = end - hitCount[end - 1];
 for(var i = end-1; i > start; i--){
  hitCount[i-1] = hitCount[i] - hitCount[i - 1];
 }

 //insert A[i]=this[i] to A2 correct position
 var insertIndex = 0;
 var insertStart = 0;
 for(var i = start; i < end; i++){
  insertIndex = hitCount[MapKey[i]];
  insertStart = insertIndex;
  while(A2[insertIndex] != null) {insertIndex++;}
  while(insertIndex > insertStart && this[i] < A2[insertIndex - 1]) {
   A2[insertIndex] = A2[insertIndex - 1];
   insertIndex--;
  }
  A2[insertIndex] = this[i];
 }
 for(var i = start; i < end; i++) {this[i] = A2[i];}
};

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

public class HashSort {

 //Размер массива исходных данных
 static int SOURCELEN = 1000000;
 int source[] = new int[SOURCELEN];
 
 //Копия исходных данных для сравнения с быстрой сортировкой
 int quick[] = new int[SOURCELEN];
 
 //Размер блока для хэширующей сортировки
 static int SORTBLOCK = 500;
 static int k = 3;
 
 //Временный массив
 static int TMPLEN = (SOURCELEN < SORTBLOCK * k) ? SORTBLOCK * k : SOURCELEN;
 int tmp[] = new int[TMPLEN];
 
 //Диапазон значений исходных данных
 static int MIN_VAL = 10;
 static int MAX_VAL = 1000000;

 int minValue = 0;
 int maxValue = 0; 
 double hashKoef = 0;
 
 //Заполнение массива исходных данных случайными значениями
 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;
  }
 }

 //Поиск минимального и максимального значений плюс вычисление коэффициента для хэш-функции
 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));
 } 
 
 //Склеивание (иначе говоря - слияние) двух смежных отсортированных частей массива
 public void stickParts(int startIndex, int mediana, int endIndex) {
  int i=startIndex;
  int j=mediana+1;
  int k=0;
  //Пока есть элементы в обоих подмассивах - производим их слияние
  while(i<=mediana && j<=endIndex) {
   if(source[i]<source[j]) {
    tmp[k] = source[i];
    i++;
   } else {
    tmp[k] = source[j];
    j++;
   }
   k++;
  }
  //Если в левом остались элементы - переносим в конец общего подмассива
  if( 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);
 }
 
 //Сдвиг вправо во временном массиве для разрешения коллизий
 //Передвигаем несколько подряд стоящих элементов чтобы слева осовободить ячейку
 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;
 } 

 //Хэш-функция для сортировки хэшированием
 public int hash(int value) {
  return (int)(((double)value - (double)minValue)*hashKoef);
 }
 
 //Вставка значений во временный массив с разрешением коллизий
 public void insertValue(int index, int value) {
  int _index = index;
  //Если место занято, то ищем правее
  //двигаемся пока заняты ячейки и вставляемый элемент больше тех что уже в хеш-массиве
  while(tmp[_index] != 0 && tmp[_index] <= value) { _index++; }
  //Если всё ещё занято и дошли до элемента, который больше вставляемого
  if( tmp[_index] != 0) {
   shiftRight(_index);//Сдвигаем подряд идущие бОльшие элементы вправо
  }
  tmp[_index] = value;//Место свободно - вставляем элемент
 }
 
 //Копирование отсортированных данных из временного массива в исходный
 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++;
   }
  }
 } 
 
 //Очистка временного массива
 public void clearTMP() {
  if( tmp.length < SORTBLOCK*k) {
   Arrays.fill(tmp, 0);
  } else {
   Arrays.fill(tmp, 0, SORTBLOCK*k, 0);
  }
 }
 
 //Хэширующая сортировка
 public void hashingSort(int startIndex, int endIndex) {
  
  //1. Поиск минимального и максимального значения с вычислением хэширующего коэффициента
  findMinMax(startIndex, endIndex);
  
  //2. Очистка временного массива
  clearTMP();
  
  //3. Вставка во временный массив с использованием хэш-функции
  for(int i=startIndex; i<=endIndex; i++) {
   insertValue(hash(source[i]), source[i]);
  }
  
  //4. Перемещение отсортированных данных из временного массива в исходный
  extract(startIndex, endIndex);
 }
 
 //Рекурсивный спуск с дихотомией до уровня блока хэширующей сортировки 
 public void sortPart(int startIndex, int endIndex) {

  //Если размер подмассива меньше 500, то непосредственно хэш-сортируем
  if((endIndex - startIndex) <= SORTBLOCK ) {
     hashingSort(startIndex, endIndex);
     return;
  }
  
  //Если размер > 500 то делим пополам и рекурсия к каждой половинке
  int mediana = startIndex + (endIndex - startIndex) / 2;
  sortPart(startIndex, mediana);//Рекурсия к левой половинке
  sortPart(mediana+1, endIndex);//Рекурсия к правой половинке
  stickParts(startIndex, mediana, endIndex);//Половинки рекурсивно отсортированы - склеиваем их
 }
 
 //Сортируем весь массив как максимально возможный подмассив
 public void sort() {
  sortPart(0, SOURCELEN-1);
 }   
 
 public static void main(String[] args) {
  HashSort hs = new HashSort();
  hs.randomize();
  hs.sort();
 }

}