## Wednesday, December 2, 2015

### LSD Radix Sort - Sorting a large number of 32 bit integers in linear time.

LSD Radix Sort with Key Indexed Counting. The algorithm runs 2-3x faster than JAVAs Arrays.sort() method which uses Dual-Pivot Quicksort.

Source:

```import java.util.Arrays;
import java.util.Random;

public class IntegersLSDBit {

public static int[] sort(int[] a, int width, int R){
int cols = width/R;
int N = a.length;
int[] aux = new int[N];

for(int i=0;i<cols;++i){
int count[] = new int[(1<<R)+1];
for(int j=0;j<N;++j){

if(i==cols-1){

if(chunk >= 0x80){
count[(chunk - 0x80) +1]++;
}else{
count[0x80 + chunk + 1]++;
}
}else count[chunk+1]++;
}

for(int j=0;j<count.length-1;++j){
count[j+1] += count[j];
}

for(int j=0;j<N;++j){

if(i==cols-1){
if(chunk >= 0x80){
aux[count[(chunk - 0x80)]++] = a[j];
}else{
aux[count[0x80 + chunk]++] = a[j];
}
}else aux[count[chunk]++] = a[j];
}
for(int j=0;j<N;++j)a[j]=aux[j];
}
return a;
}

public static void main(String[] args){
int[] a = new int[10000000];
int[] a2 = new int[10000000];

Random rand = new Random();
for(int i=0;i<a.length;++i){
a[i] = rand.nextInt();
a2[i] = a[i];
}

double start1 = System.nanoTime();
a = sort(a, 32, 8);
//        System.out.println(Arrays.toString(a));
double time1 = System.nanoTime()-start1;

double start2 = System.nanoTime();
Arrays.sort(a2);
//        System.out.println(Arrays.toString(a2));
double time2 = System.nanoTime()-start2;
//
System.out.println("LSD time : "+time1/10e6+"ms Arrays.sort() time : "+time2/10e6+"ms Arrays.sort()/LSD = "+(time2/time1));

for(int i=0;i<a.length;++i)if(a[i]!=a2[i]){System.out.println("Outputs dont match");break;}
}
}```

Output:

LSD time : 47.4179334ms Arrays.sort() time : 110.8756467ms Arrays.sort()/LSD = 2.338264001610834