Jon Bentley's bitmap sort implementation
An idea: I'd try to implement the algorithm with bigger data types (int, long) instead of the byte.

Some notes:


I'd create a BYTE_SIZE constant for 8, try to avoid magic numbers.

private static final int BYTE_SIZE = 8;


It would help a lot if you change from byte to another data type.
The return type of sortDistinctIntegers is really confusing. It returns with the first argument. Users easily could believe that it returns another array despite the fact that it modifies the input array. Make it void.
For easier readability I'd 


extract out some method for easier readability: createBitmapArray, processBitmapByte, doSort,
use longer variable and parameter names (outputIndex instead of k, bitmapSize instead of N, bitIndex instead of j),
create local variables for 1 &lt;&lt; bitIndex (mask), etc.



Below is the code after a few refactoring steps. (I haven't checked that the algorithm is correct or not.)

private static final int BYTE_SIZE = 8;

public void sortDistinctIntegers(final int[] data, final int min, final int max) {
    final byte[] bitmap = createBitmapArray(data, min, max);

    doSort(data, min, bitmap);
}

private byte[] createBitmapArray(final int[] data, final int min, 
        final int max) {
    final int bitmapSize = (int) (((long) max - min) / BYTE_SIZE + 1);
    final byte[] bitmap = new byte[bitmapSize];

    for (int i = 0; i &lt; data.length; i++) {
        final long min2 = (long) data[i] - min; // TODO: need a better name
        final int mask = 1 &lt;&lt; (int) (min2 % BYTE_SIZE);
        bitmap[(int) (min2 / BYTE_SIZE)] |= mask;
    }
    return bitmap;
}

private void doSort(final int[] data, final int min, final byte[] bitmap) {
    int outputIndex = 0;
    for (int bitmapArrayIndex = 0; bitmapArrayIndex &lt; bitmap.length; 
            bitmapArrayIndex++) {
        final byte currentBitmapByte = bitmap[bitmapArrayIndex];
        outputIndex = processBitmapByte(data, min, currentBitmapByte, 
                outputIndex, bitmapArrayIndex);
    }
}

private int processBitmapByte(final int[] data, final int min, 
        final byte currentBitmapByte, int outputIndex,
        final int bitmapArrayIndex) {
    for (int bitIndex = 0; bitIndex &lt; BYTE_SIZE; bitIndex++) {
        final int mask = 1 &lt;&lt; bitIndex;
        final boolean flagSet = (currentBitmapByte &amp; mask) &gt; 0;
        if (flagSet) {
            data[outputIndex] = bitmapArrayIndex * BYTE_SIZE + bitIndex + min;
            outputIndex++;
        }
    }
    return outputIndex;
}