Over a million developers have joined DZone.
Platinum Partner

Fast O(n) Integer Sorting Algorithm

· Java Zone

The Java Zone is brought to you in partnership with ZeroTurnaround. Discover how you can skip the build and redeploy process by using JRebel by ZeroTurnaround.

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:


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) {
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));

int[] list2 = Arrays.copyOf(list1, arrLength);

list2 = Arrays.copyOf(list1, arrLength);
LinearSort.sort(list2, 0, maxInteger);

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

The Java Zone is brought to you in partnership with ZeroTurnaround. Discover how you can skip the build and redeploy process by using JRebel by ZeroTurnaround.


{{ parent.title || parent.header.title}}

{{ parent.tldr }}

{{ parent.urlSource.name }}