snippetjavaMinor

Jon Bentley's bitmap sort implementation

Submitted by: @import:stackexchange-codereview·Mar 10, 2026·

Viewed 0 times

implementationbentleyjonbitmapsort

Problem

I've implemented Jon Bentley's bitmap sorting algorithm from Column 1 of his Programming Pearls book. This code supports user-defined integer range (works from Integer.MIN_VALUE to Integer.MAX_VALUE), but for now only works on a distinct set of integers.

In order to avoid overflow in the integer arithmetic, I use type-casting for intermediate results.

For anyone interested, I've also posted the full description of the algorithm and performance analysis here.

public int[] sortDistinctIntegers(int[] a, int min, int max){

    int N = (int)(((long)max-min) / 8 + 1);
    byte[] bitmap = new byte[N];

    for(int i = 0; i  0){
                a[k] = i * 8 + j + min;
                k++;
            }
        }
    }

    return a;
}

I was wondering if anyone has any comments or ideas on how to improve this code (in terms of prettification, readability and performance).

Solution

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

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  0;
        if (flagSet) {
            data[outputIndex] = bitmapArrayIndex * BYTE_SIZE + bitIndex + min;
            outputIndex++;
        }
    }
    return outputIndex;
}

Code Snippets

private static final int BYTE_SIZE = 8;

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 < data.length; i++) {
        final long min2 = (long) data[i] - min; // TODO: need a better name
        final int mask = 1 << (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 < 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 < BYTE_SIZE; bitIndex++) {
        final int mask = 1 << bitIndex;
        final boolean flagSet = (currentBitmapByte & mask) > 0;
        if (flagSet) {
            data[outputIndex] = bitmapArrayIndex * BYTE_SIZE + bitIndex + min;
            outputIndex++;
        }
    }
    return outputIndex;
}

Context

StackExchange Code Review Q#8613, answer score: 4

Revisions (0)

No revisions yet.