Radix sort with integer divisions 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 &lt; maxDigits; ++pos) {
            List&lt;List&lt;Integer&gt;&gt; buckets = splitToBuckets(arr, divisor, radix);
            flattenBuckets(arr, buckets);
            divisor *= radix;
        }
        List&lt;List&lt;Integer&gt;&gt; buckets = splitBySign(arr);
        flattenBuckets(arr, buckets);
    }

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

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

    private static void flattenBuckets(int[] arr, List&lt;? extends List&lt;Integer&gt;&gt; buckets) {
        int i = 0;
        for (List&lt;Integer&gt; 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 &gt; 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 &lt; 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?
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 &gt; 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 &gt; 0) {
        work /= radix;
        ++count;
    }
    return count;
}


Optimize

This step is a bit wasteful:


    List&lt;List&lt;Integer&gt;&gt; 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 &gt;= 0; --i) {
        int num = arr[i];
        if (num &gt; 0) {
            arr[back--] = num;
        } else {
            negative[negativeFront++] = num;
        }
    }
    System.arraycopy(negative, 0, arr, 0, negativeFront);
}