I have the need for load balancing in my MSD-radix sort routine and doing it optimally is not an option. So I tried to play with two simple routines for putting integers into a prespecified amount of buckets such that the sums of buckets are close to each other.My main question is: Can you suggest more optimal, polynomial-time algorithm for doing this. (I think my needs can tolerate at most \$\mathcal{O}(n^2)\$.)Java implementation follows:LoadBalancer.java:package net.coderodde.alg;import java.util.ArrayList;import java.util.Arrays;import java.util.List;import java.util.Random;/** * This class defines two simple routines for putting integers into specified * amount of buckets such that the sums of buckets are close to each other. * However, these are approximations, but run in linearithmic  * (<tt>O(n log n)</tt>)time each. */public class LoadBalancer {    private static final int MAXIMUM_PRINT_ARRAY_LENGTH = 50;    private static final int BAR_LENGTH = 80;    /**     * This is a basic approximation routine for distributing integers in     * <code>array</code>  into <code>buckets</code> buckets. It works by      * sorting the clone array into ascending order and loading from left to     * right into each bucket until each bucket becomes full.     *      * @param  input   the array of input integers. Is not modified.     * @param  buckets the amount of buckets.     *      * @return         a partition, which is a list of lists, each representing     *                 a bucket.     */    public static List<List<Integer>> partition1(final int[] input,                                                 final int buckets) {        checkIntArray(input);        checkBucketAmount(buckets);        final int[] array = input.clone();        final List<List<Integer>> ret = new ArrayList<>(buckets);        for (int i = 0; i < buckets; ++i) {            ret.add(new ArrayList<>());        }        Arrays.sort(array);        int totalArraySum = 0;        for (final int integer : array) {            totalArraySum += integer;        }        final int MINIMUM_BUCKET_LOAD = totalArraySum / buckets;        int integerIndex = 0;        int bucketIndex = 0;        int loaded = 0;        // Load the buckets.        while (integerIndex < array.length) {            while (integerIndex < array.length && loaded < MINIMUM_BUCKET_LOAD) {                final int currentInteger = array[integerIndex++];                ret.get(bucketIndex).add(currentInteger);                loaded += currentInteger;            }            // Proceed to the next bucket.            ++bucketIndex;            loaded = 0;        }        return ret;    }    /**     * This is a basic approximation routine for distributing integers in     * <code>array</code>  into <code>buckets</code> buckets. It works by      * sorting the clone array into ascending order and then loads to the first     * bucket the smallest integer, the largest integer, the second smallest     * integer, the second largest integers, and so on until each bucket becomes     * full.     *      * @param  input   the array of input integers. Is not modified.     * @param  buckets the amount of buckets.     *      * @return         a partition, which is a list of lists, each representing     *                 a bucket.     */    public static List<List<Integer>> partition2(final int[] input,                                                 final int buckets) {        checkIntArray(input);        checkBucketAmount(buckets);        int[] array = input.clone();        final List<List<Integer>> ret = new ArrayList<>(buckets);        for (int i = 0; i < buckets; ++i) {            ret.add(new ArrayList<>());        }        Arrays.sort(array);        int totalArraySum = 0;        for (final int integer : array) {            totalArraySum += integer;        }        final int MINIMUM_BUCKET_LOAD = totalArraySum / buckets;        final int[] work = new int[array.length];        int workIndex = 0;        int leftIndex = 0;        int rightIndex = array.length - 1;        // Put to work smallest integer, then the largest integer,        // then the second smallest integer, then second largest integer, and        // so on.        while (leftIndex < rightIndex) {            work[workIndex++] = array[leftIndex++];            work[workIndex++] = array[rightIndex--];        }        // If the array has odd length, we need to copy to work the middle         // element.        if (leftIndex == rightIndex) {            work[workIndex] = array[leftIndex];        }        array = work;        int integerIndex = 0;        int bucketIndex = 0;        int loaded = 0;        // Load the buckets.        while (integerIndex < array.length) {            while (integerIndex < array.length && loaded < MINIMUM_BUCKET_LOAD) {                final int currentInteger = array[integerIndex++];                ret.get(bucketIndex).add(currentInteger);                loaded += currentInteger;            }            // Proceed to the next bucket.            ++bucketIndex;            loaded = 0;        }        return ret;    }    public static void main(final String... args) {        final int SIZE = 30;        final int MAX = 100;        final long SEED = System.currentTimeMillis();        final int BUCKET_AMOUNT = 5;        final Random rnd = new Random(SEED);        System.out.println(Seed:  + SEED);        final int[] array = getRandomIntegerArray(SIZE, MAX, rnd);        List<List<Integer>> partition = partition1(array, BUCKET_AMOUNT);        println(array);        System.out.println(Sum:  + sum(array));        printBar();        printPartition(partition);        System.out.println(Sum of pairwise differences:  +                countPairwiseDifferenceSums(partition));        printBar();        partition = partition2(array, BUCKET_AMOUNT);        printPartition(partition);        System.out.println(Sum of pairwise differences:  +                countPairwiseDifferenceSums(partition));    }    /**     * Returns a random array of nonnegative integers.     *      * @param size the length of the array.     * @param max  the maximum value of a array component.     * @param rnd  the random number generator.     *      * @return a random array of integers.     */    private static int[] getRandomIntegerArray(final int size,                                               final int max,                                               final Random rnd) {        final int[] array = new int[size];        for (int i = 0; i < size; ++i) {            array[i] = rnd.nextInt(max + 1);        }        return array;    }    /**     * Counts the sum of absolute differences between all the integer buckets.     *      * @param buckets the list of buckets, where each bucket is represented by     *                a list of integers.     * @return        the sum of bucket differences.     */    private static int countPairwiseDifferenceSums(            final List<List<Integer>> buckets) {        final int[] bucketSumArray = new int[buckets.size()];        for (int index = 0; index < bucketSumArray.length; ++index) {            for (final Integer i : buckets.get(index)) {                bucketSumArray[index] += i;            }        }        int sum = 0;        for (int i = 0; i < bucketSumArray.length - 1; ++i) {            for (int j = i + 1; j < bucketSumArray.length; ++j) {                sum += Math.abs(bucketSumArray[i] - bucketSumArray[j]);            }        }        return sum;    }    /**     * Prints a funky separation bar.     */    private static void printBar() {        final StringBuilder sb = new StringBuilder();        for (int i = 0; i < BAR_LENGTH; ++i) {            sb.append('-');        }        System.out.println(sb.toString());    }    /**     * Prints information about the input partition.     *      * @param partition the partition to print.     */    private static void printPartition(final List<List<Integer>> partition) {        int totalSum = 0;        for (final List<Integer> bucket : partition) {            System.out.print([);            int sum = 0;            for (int i = 0; i < bucket.size(); ++i) {                System.out.print(bucket.get(i));                if (i < bucket.size() - 1) {                    System.out.print(, );                }                sum += bucket.get(i);            }            System.out.println(] Sum:  + sum);            totalSum += sum;        }        System.out.println(Total element sum:  + totalSum);    }    /**     * Prints the entire integer array on a single line.     *      * @param array the array to print.     */    private static void println(final int[] array) {        if (array.length > MAXIMUM_PRINT_ARRAY_LENGTH) {            System.out.println((The array is too large to print!));            return;        }        System.out.print([);        for (int i = 0; i < array.length; ++i) {            System.out.print(array[i]);            if (i < array.length - 1) {                System.out.print(, );            }        }        System.out.println(]);    }    /**     * Returns the sum of integers within the input array.     *      * @param  array the array to sum.     *      * @return the sum of integers.     */    private static int sum(final int[] array) {        int sum = 0;        for (final int i : array) {            sum += i;        }        return sum;    }    private static void checkIntArray(final int[] array) {        if (array == null) {            throw new IllegalArgumentException(                    The integer array reference is null.);        }    }    private static void checkBucketAmount(final int buckets) {        if (buckets < 1) {            throw new IllegalArgumentException(                    At least one bucket is required. Received  + buckets);        }    }}
Approximately putting integers into buckets such that the sum of bucket differences is minimized
java;combinatorics