Radix sort with integer divisions

Question

Here's a perhaps naive but simple implementation of Radix sort in Java. It works with any radix, and both positive and negative numbers.

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

public class RadixSortWithDivision {

    public static final int DEFAULT_RADIX = 10;

    public static void sort(int[] arr) {
        sort(arr, DEFAULT_RADIX);
    }

    public static void sort(int[] arr, int radix) {
        int maxDigits = 1 + (int) (Math.log(max(arr)) / Math.log(radix));
        int divisor = 1;
        for (int pos = 0; pos < maxDigits; ++pos) {
            List<List<Integer>> buckets = splitToBuckets(arr, divisor, radix);
            flattenBuckets(arr, buckets);
            divisor *= radix;
        }
        List<List<Integer>> buckets = splitBySign(arr);
        flattenBuckets(arr, buckets);
    }

    private static List<List<Integer>> splitToBuckets(int[] arr, int divisor, int radix) {
        List<List<Integer>> buckets = new ArrayList<>();
        for (int i = 0; i < radix; ++i) {
            buckets.add(new LinkedList<>());
        }
        for (int num : arr) {
            int bucketIndex = Math.abs(num) / divisor % radix;
            buckets.get(bucketIndex).add(num);
        }
        return buckets;
    }

    private static List<List<Integer>> splitBySign(int[] arr) {
        List<Integer> positive = new LinkedList<>();
        List<Integer> negative = new LinkedList<>();
        for (int num : arr) {
            if (num >= 0) {
                positive.add(num);
            } else {
                negative.add(0, num);
            }
        }
        return Arrays.asList(negative, positive);
    }

    private static void flattenBuckets(int[] arr, List<? extends List<Integer>> buckets) {
        int i = 0;
        for (List<Integer> bucket : buckets) {
            for (int num : bucket) {
                arr[i++] = num;
            }
        }
    }

    private static int max(int[] arr) {
        int max = Integer.MIN_VALUE;
        for (int num : arr) {
            if (num > max) {
                max = num;
            }
        }
        return max;
    }
}

Unit tests:

import org.junit.Test;

import java.util.Arrays;
import java.util.Random;

import static org.junit.Assert.assertArrayEquals;

public abstract class SortTest {

    abstract void sort(int[] arr);

    private int[] newRandomArray(int num) {
        Random random = new Random(0);
        int[] arr = new int[num];
        for (int i = 0; i < arr.length; ++i) {
            arr[i] = random.nextInt();
        }
        return arr;
    }

    private void sortAndVerify(int[] arr) {
        int[] copy = arr.clone();
        Arrays.sort(copy);
        sort(arr);
        assertArrayEquals(copy, arr);
    }

    @Test
    public void test_empty() {
        sortAndVerify(new int[0]);
    }

    @Test
    public void test_1() {
        sortAndVerify(new int[]{1});
    }

    @Test
    public void test_1_2() {
        sortAndVerify(new int[]{1, 2});
    }

    @Test
    public void test_2_1() {
        sortAndVerify(new int[]{2, 1});
    }

    @Test
    public void test_1_2_3() {
        sortAndVerify(new int[]{1, 2, 3});
    }

    @Test
    public void test_3_2_1() {
        sortAndVerify(new int[]{3, 2, 1});
    }

    @Test
    public void test_random_10() {
        sortAndVerify(newRandomArray(10));
    }

    @Test
    public void test_random_1000() {
        sortAndVerify(newRandomArray(1000));
    }

}


public class RadixSortWithDivisionTest extends SortTest {
    @Override
    void sort(int[] arr) {
        RadixSortWithDivision.sort(arr);
    }
}

How would you improve this?

How would you improve the unit test cases?

Answer 1

I spotted a possible bug. You set maxDigits like this:

int maxDigits = 1 + (int) (Math.log(max(arr)) / Math.log(radix));

The problem is that max(arr) is the largest element in the array, and it could be unsuitable to be passed to Math.log(). Suppose the array contained only negative numbers. In that case, Math.log() would return NaN. If the max element were zero, it would return negative infinity.

I suggest first that max() should return the maximum of the absolute values of the array. After that, I suggest either checking for zero as a special case, or using a simple loop to calculate maxDigits instead of using log().

I guess this also partially answers the question of how to improve unit tests: make a case with all negative numbers.

Answer 2

Bugs

@JS1's answer was spot-on: the counting of digits this way was buggy:

    int maxDigits = 1 + (int) (Math.log(max(arr)) / Math.log(radix));

Because Math.log(...) gives NaN for negative numbers, and negative infinity for 0, which breaks the digit count and the sorting.

This unit test exposed the bug:

@Test
public void test_m300_m200_m999() {
    sortAndVerify(new int[]{-30, -200, -999});
}

I could fix this by finding the max absolute value.

private static int getMaxAbs(int[] arr) {
    int maxAbs = 0;
    for (int num : arr) {
        int absNum = Math.abs(num);
        if (absNum > maxAbs) {
            maxAbs = absNum;
        }
    }
    return maxAbs;
}

---

There is another bug, related to floating point arithmetics. Even after taking the max of absolute values for counting digits, this test still fails:

@Test
public void test_m300_m200_m1000() {
    sortAndVerify(new int[]{-300, -200, -1000});
}

The problem is that Math.log(1000) / Math.log(10) doesn't give 3 as expected, but 2.9999999999999996, which then gets truncated to 2 in the line that calculates maxDigits.

The fix for this is to count the digits in a simple loop instead of using divisions with Math.log that is prone to floating point arithmetic issues:

private static int countDigits(int num, int radix) {
    if (num == 0) {
        return 1;
    }
    int work = num;
    int count = 0;
    while (work > 0) {
        work /= radix;
        ++count;
    }
    return count;
}

Optimize

This step is a bit wasteful:

    List<List<Integer>> buckets = splitBySign(arr);
    flattenBuckets(arr, buckets);

The splitting step will visit all elements to create the buckets, and then the flatting step will visit all elements again to write back to the array.

A more efficient approach is possible:

• Create a helper array to store the negative numbers in the right order
• Iterate from the back of the target array
  • If the current item is negative, write it to the next position in the helper array
  • If the current item is positive, write it to the next position from the back of the target array
• After one pass, the positive numbers will be clustered at the end of the target array, in the correct order, and the negative numbers will be at the beginning of the helper array
• Copy the beginning of the helper array to target

Implementation:

private static void reverseAndShiftNegatives(int[] arr) {
    int len = arr.length;
    int[] negative = new int[len];
    int negativeFront = 0;
    int back = len - 1;
    for (int i = back; i >= 0; --i) {
        int num = arr[i];
        if (num > 0) {
            arr[back--] = num;
        } else {
            negative[negativeFront++] = num;
        }
    }
    System.arraycopy(negative, 0, arr, 0, negativeFront);
}