Sunday, April 02, 2006

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);
//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) {
for (int j = 0; j < temp[ind]; j++) {
toSort[i++] = value;


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.


Post a Comment

<< Home