BeadSort.java

public class BeadSort {
    private static final int BEAD = 1;

    public void sort(int[] array) {
        int[][] abacus = populateAbacusAndWipeInput(array);

        for (int pole = 0; pole < abacus[0].length; pole++) {
            int poleRow = abacus.length - 1;
            for (int currentRow = poleRow; currentRow >= 0; currentRow--) {
                if (abacus[currentRow][pole] == BEAD) {
                    array[poleRow] += 1; //increment as this row has 1 bead on the pole
                    poleRow--;
                }
            }
        }
    }

    private int[][] populateAbacusAndWipeInput(int[] array) {
        int rowsRequired = array.length;
        int polesRequired = getMax(array);

        int[][] abacus = new int[rowsRequired][polesRequired];

        for (int row = 0; row < abacus.length; row++) {
            int itemToPlaceOnAbacus = array[row];
            for (int pole = 0; pole < itemToPlaceOnAbacus; pole++) {
                abacus[row][pole] = BEAD;
            }
            array[row] = 0; // wipe out element
        }
        return abacus;
    }

    private int getMax(int[] arr) {
        int max = 0;

        for (int i = 0; i < arr.length; i++) {
            if (arr[i] > max)
                max = arr[i];
        }

        return max;
    }
}

This is O(S)