**Update**: This post was reposted @ dzone with lots of upvotes – Thanks!

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

Pingback: Сортировка за O(N)-время | О программировании

Math.abs(rand.nextInt(maxInteger)) should be written as just rand.nextInt(maxInteger)