Algorithms – How to Split and Sort Numbers into Three Equally Large Groups

Intuitively, even though your constaints are relaxed, I think your problem is an instance of the bin packing problem, which is NP-hard. Perhaps you should ask the CS Theory group whether this is an instance of BPP/generalized BPP.

Your greedy algorithm works in linearithmic complexity (sorting in O(n log n), binning in O(n log log n), assuming using heaps, because your number of bins is ~ log n), but it is not optimal (easy to find sequences which trick it).

You can do a best-fit greedy in O(n log log n) - find the mean of the numbers in linear time (without sorting), and then for each number try to fit it in a bin such that current average stays as close as possible to the total average - this should be a log-logarithmic operation with respect to n. Whether this is an appropriate solution for your problem depends on how far from optimal you can afford to be.

However, note that you can't go better than this O(n log log n) - because whatever clever scheme you use, you will need to pick each element up, and bin it.

I created a partitioning program with space usage O(1) but running time O(N^2). You can find the source code here. In the comments there is a good explanation of the shuffling algorithm used.

The key part of this program is the shuffling step, which is the step that takes O(N^2) time. Doc Brown asked "how can you shuffle N elements in less than O(N) space"? I extracted the shuffling logic and created a separate program which is listed below.

To get the full explanation, please refer to the source code linked above. The following is a brief explanation:

The shuffling function simulates a Fisher-Yates shuffle, where you swap the array[0] with array[r], where r is a random number in the range [0..N-1]. Then you swap array[1] with array[r], where r is a new random number in the range [1..N-1]. You keep moving down the array, swapping random elements, until you reach the end of the array.

To use O(1) space, there is no array. Instead, for each new random element that we select, we need to replay the previous swaps in backwards order in order to figure out where the array element really came from. In essence, we pick a random element, and then we undo the swaps that came before it to determine where the original position of the element was. We can replay the previous swaps by simply reseeding the random number generator back to a previously saved seed.

Edit: After posting this solution, I found this stackoverflow question which lists some better ways to create a permutation of N numbers in constant space. So if you substitute one of those solutions in for my shuffling function, you can do better than O(N^2) time and still use O(1) space.

/* Given a number N, shuffle the elements from 0..N-1 and print them. */
/* This algorithm uses O(1) space but uses O(N^2) time.               */
#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include <time.h>

static void shuffle(int n);

int main(int argc, char *argv[])
{
    if (argc < 2) {
        printf("Usage: shuffle N\n");
        exit(0);
    }

    shuffle(atoi(argv[1]));
    return 0;
}

static void shuffle(int n)
{
    uint32_t seedOriginal = time(NULL);
    uint32_t seed         = 0;
    int      i            = 0;
    int      j            = 0;
    int      slot         = 0;

    for (i=0;i<n;i++) {
        seed = seedOriginal;
        srand(seed);

        // Skip n-i-1 random numbers.
        for (j=n-i-1;j>0;j--)
            rand();

        // Select an array slot from [i..n-1].
        slot = i + (rand() % (n - i));

        // Find out what that slot corresponds to in the original order.
        // We do this by backtracking through all the previous steps.
        for (j=i-1;j>=0;j--) {
            int r = j + (rand() % (n - j));

            // Every time we see the slot we are looking for, we switch
            // to looking for slot j instead, because at this previous step
            // we swapped array[j] with array[slot].
            if (r == slot)
                slot = j;
        }

        // Slot is now the correct element we are looking for.
        printf("%d\n", slot);
    }
}