Sort a byte array in Java

The default algorithm used to sort a byte array is Arrays.sort(byte [] array). The algorithm used is a quicksort (complexity about =(nlog(n))). It is good for objects, but we have seen it is far better to use a countingsort algorithm.

Here is the code used:

    public static void sort(byte toSort[], int offset, int length) {

        //If we have less than this number of elements, we do the
        //default sort else we use the countingsort algorithm
        if (length < 45) {
            Arrays.sort(toSort, offset, length);
            return;
        }
        //It can go faster if we keep in memory an other array, 
        // but the class has to be synchronized.
        //We initialize a new array
        int temp [] = new int[256];
        Arrays.fill(temp, 0);

        //Count the number of elements
        for (int i = offset; i < offset + length; i++) {
            temp[toSort[i] + 128]++;
        }
        byte value = -128;
        int ind = 0;
        //Insert the bytes in the good order
        for (int i = offset; i < offset + length;) {
            while (temp[ind] == 0) {
                ind++;
                value++;
            }
            for (int j = 0; j < temp[ind]; j++) {
                toSort[i++] = value;
            }
            value++;
            ind++;

        }
    }

If there is less than 45 elements we have found that creating new arrays takes to much time and that the countingsort algorithm is not good enough.

The factor (sun sort)/countingsort has been calculated for some size of arrays. With 80 elements, the couting sort is about 50% faster. At 1280 elements, the couting sort algorithm is 4 times faster.