Fast O(n) Integer Sorting Algorithm

yesterday i learned that there is an o(n) integer sort algorithm (i should have read this before in a basic algorithm book :-/).

now i wondered: is this necessary in real applications? e.g. somewhere in java? today i have taken the counting sort and i can argue: yes, you should use integer sort especially for large arrays!

and when in detail should you apply the fast integer sort? apply it if

• you have positive integer values to sort. the requirement ‘positive’ and ‘integer’ is necessary for the listed o(n) algorithm, but not if you implement your own possible better solution .
• you have a limited interval for the integer values (preferable min and max=m should be known before you sort)
  e.g. if you know the maximum integer number in your array will be m=10^7 then you should use the integer sort if the array length n is roughly greater than m/2500 = 40000. this linear equation should hold true (for some values ), because quick sort is nearly independent of m and the time-offset for integer sort increases nearly linear with m as you can see in the graph

now take a look at the graph where y =time in seconds for 10 runs and x =array length:

conclusion

i would apply this sorting algorithm only for n>10^7 where the difference between quicksort and integer sort could lay in the range of seconds. the memory consumption was not measured but should be ~twice times higher for the fast integer sort.

java sourcecode

//class linearsort
public static void main(string[] args) {

 // init jvm
 new linearsort().start(1000, 10000, 10000);
 new linearsort().start(1000, 10000, 10000);

 // run performance comparison
 for (int maxinteger = 1000; maxinteger < 100000000; maxinteger *= 3) {
  for (int arrlength = 1000; arrlength < 100000000; arrlength *= 3) {
   system.gc();
   new linearsort().start(arrlength, maxinteger, 10);
  }
 }
}

 private random rand = new random();

 // stop watch for integer sort with *unknown* range. marked as lin in the plot
 private simpletimer linearstopwatch = new simpletimer();</pre>

 // stop watch for integer sort with known range. marked as lin' in the plot
 private simpletimer linearknownstopwatch = new simpletimer();

 private simpletimer qsortstopwatch = new simpletimer();

 private void start(int arrlength, int maxinteger, int times) {
 for (int count = 0; count < times; count++) {
   int[] list1 = new int[arrlength];
   for (int i = 0; i < arrlength; i++) {
     // do only allow positive integers until the specified 'max'-value
     list1[i] = math.abs(rand.nextint(maxinteger));
   }
   linearstopwatch.start();
   linearsort.sort(list1);
   linearstopwatch.pause();

   int[] list2 = arrays.copyof(list1, arrlength);
   qsortstopwatch.start();
   arrays.sort(list2);
   qsortstopwatch.pause();

   list2 = arrays.copyof(list1, arrlength);
   linearknownstopwatch.start();
   linearsort.sort(list2, 0, maxinteger);
   linearknownstopwatch.pause();
 }

 system.out.println(maxinteger + ";" + arrlength + ";" + linearstopwatch
 + ";" + linearknownstopwatch
 + ";" + qsortstopwatch); // + ";" + qsortliststopwatch);
}

 static int[] sort(int[] array, int min, int max) {
   //the range is useful to minmize the memory usage
   //countintegers holds the number of each integer
   int[] countintegers = new int[max - min + 1];

   for (int i = 0; i < array.length; i++) {
     countintegers[array[i] - min]++;
   }

   int insertposition = 0;
   //fill array in sorted order
   for (int i = min; i <= max; i++) {
     for (int j = 0; j < countintegers[i - min]; j++) {
       array[insertposition++] = i;
     }
   }
   return array;
 }

 static int[] sort(int[] array) {
   int min, max = min = array[0];
   //determine the max and min in the array
   for (int i = 1; i < array.length; i++) {
     if (array[i] < min)
       min = array[i];

     if (array[i] > max)
       max = array[i];
   }
   return sort(array, min, max);
 }

 //class simpletimer

 private long laststart = -1;
 private long time;

 public void start() {
   if (laststart != -1)
     throw new illegalstateexception("call stop before!");

   laststart = system.currenttimemillis();
 }

 public void pause() {
   if (laststart < 0)
     throw new illegalstateexception("call start before!");

   time = time + (system.currenttimemillis() - laststart);
   laststart = -1;
 }

 public string tostring() {
   return time / 1000f + "";
 }

from http://karussell.wordpress.com