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 mask = 0xff; 
        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){
                int chunk = (a[j]>>i*R)&mask; 
                
                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){ 
                int chunk = (a[j]>>i*R)&mask;
                
                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