# Fast O(n) Integer Sorting Algorithm

· Java Zone · Interview
Save
29.72K Views

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 linearsortpublic 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;   //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

Topics:

Opinions expressed by DZone contributors are their own.