Fastest sorting of integers
Posted on 17 September 2016
Problem
We are given a huge array of bounded, nonduplicate, positive integers that need to be sorted. Whatâ€™s the fastest way to do it.
Solution
Most of the interview candidates that I have talked to about this problem come up
with the quick answer as MergeSort
or divideandconquer. The cost of sorting
being O(N * Log(N))
 which in this case is not the fastest sorting time.
The fastest time to sort an integer array is O(N)
. Let me explain how.
 Construct a boolean array of length N
 For every integer
n
in array, mark the boolean at indexn
in array astrue
 Once the array iteration is complete, just iterate over the boolean array again
to print all the indices that have the value set as
true
public void sortBoundedIntegers(int[] array) {
/// the regular checks first
if(array == null) {
return;
}
if(array.length == 0) {
return;
}
// build the boolean result array
boolean[] result = new boolean[array.length];
for(int index = 0; index < array.length; index++) {
int num = array[index];
result[num] = true;
}
// print the result
for(int index = 0; index < result.length; index++) {
if(result[index]) {
System.out.println(index);
}
}
}
Additional constraints and optimizations available

A
boolean
occupies onebyte of memory. Thus, switching to a bitvector (also called as bitarray) will reduce the memory consumption by a factor of 8. Check code sample 2. 
In case the integers are also negative, another bitarray can be used to check for negatives, and then both iterated oneafteranother to produce result. Check code sample 2.

To further reduce the memory consumption, one can make use of sparsedbitarrays. This can lead to huge drop in memory consumption if the integers are spaced apart a lot. Check code sample 2. Refer to brettwooldridge/SparseBitSet for one such implementation.

In case the integer array contains duplicates, use a small
short
array than theboolean
array to hold the number of times an integer has been seen, thus still sorting inO(N)
time.
Code Sample 2
public void sortBoundedIntegers(int[] array) {
// run regular checks
final int len = array.length;
// considering SparsedBitSet is an implementation available
BitSet negative = new SparsedBitSet(len);
BitSet positive = new SparsedBitSet(len);
// sort
for(int index = 0; index < len; index++) {
int num = array[index];
if(num < 0) {
num = 0  num; // convert to positive
negative.setBit(num, true);
} else {
positive.setBit(num, true);
}
}
// output
int index = 1;
do {
index = negative.getNextSetBit(index);
if(index < 0) {
break;
}
System.out.println(0  index);
} while(true);
index = 1;
do {
index = positive.getNextSetBit(index);
if(index < 0) {
break;
}
System.out.println(index);
} while(true);
}