Sorting in "linear" time with Radix Sort

int[] c=new int[10];

int[] count=new int[4]; // count[i] is set = 0 foreach i when declaring
int[] pref=new int[4]; // this is a support array that calcs the prefixes
int[] t=new int[c.Length]; // target array

for (int i=0; i<c.Length; i++) {
    count[c[i]]++;
}

pref[0]=0;
for (int i=1; i<count.Length; i++) {
    pref[i]=pref[i-1]+count[i-1];
}

for (int i=0; i<t.Length; i++) {
    t[pref[c[i]]++]=c[i];
}

c.Length = 8
    **_ *_* _**
329 720 720 329
457 355 329 355
675 436 436 436
839 457 839 457
436 657 355 657
720 329 457 720
355 839 657 839

// d is the number of digits
// l is total digits of maximum key
// hence l/d is the number of our groups

RadixSort(c, d) {
    for i<-1 to Ceiling(l/d)
    do use a stable sort to sort group i of array c numbers
}

// array a is to be sorted and it's implicitly passed by reference to the RadixSort method

private void RadixSort(int[] a) {
    
    // our helper array
    int[] t=new int[a.Length];
    
    // number of bits our group will be long
    int r=4; // try to set this also to 2, 8 or 16 to see if it is quicker or not
    
    // number of bits of a C# int (sizeof works with unsafe code so I did this way...)
    int b=(int)Math.Ceiling(Math.Log(int.MaxValue,2))+1;
    
    // counting and prefix arrays (note dimensions 2^r which is the number of all possible values of a r-bit number)
    int[] count=new int[1<<r];
    int[] pref=new int[1<<r];
    
    // number of groups
    int groups=(int)Math.Ceiling((double)b/(double)r);
    
    // the mask to identify groups
    int mask = (1<<r)-1;
    
    // the algorithm:
    for (int c=0, shift=0; c<groups; c++, shift+=r) {
        // reset count array
        for (int j=0; j<count.Length; j++) {
            count[j]=0;
        }
        // counting elements of the c-th group
        for (int i=0; i<a.Length; i++) {
            count[(a[i]>>shift)&mask]++;
        }
        // calculating prefixes
        pref[0]=0;
        for (int i=1; i<count.Length; i++) {
            pref[i]=pref[i-1]+count[i-1];
        }
        // from a[] to t[] elements ordered by c-th group
        for (int i=0; i<a.Length; i++) {
            t[pref[(a[i]>>shift)&mask]++]=a[i];
        }
        // a[]=t[] and start again until the last group
        a=(int[])t.Clone();
    }
    // a is sorted
}