нужен алгоритм

Могу предложить простой вариант.

// (c) %username%, GNU GPL3+, идея и реализация

signed int *number_array; // - фсе там, не NULL;
int number_array_length; //- размерчик массива сверху. лимит до 2Гб, не ноль, не 1.
signed int balance = 0;

unsigned int *sortarray = NULL;
sortarray = new int [number_array_length*2];
if (sortarray == NULL) return(-1);

int counter_right=0;
int counter_left=0;

for (int IP=0; IP<number_array_length;>=0) { sortarray[IP][0]=number_array[IP]; balance=balance-number_array[IP]; counter_right++;}
else { sortarray[IP][1] = number_array[IP]; balance=balance+number_array[IP]; counter_left++;}

}

тута нужно забрать эти числа из sortarray.
Те что правые - в sortarray[][0],их количество в counter_right, те что левые в sortarray[][1], количество в counter_left.

delete sortarray;
--------------

Что делает это алгоритм. Это алгоритм алкаша. В одной руке одна бутылка, в другой другая. На алкаша льется вино.
Есть переменная баланс. Если баланс нулевой или положительный, направляем струю в правую руку, и баланс кренится вправо - те в отрицательную сторону.
Если баланс отрицательный (другой) , то направляем струю в левую руку и баланс кренится влево - те в положительную сторону.
И так пока вино не перестанет лить. Те, он их шатаясь расбрасывает.

Алгоритм быстрый, грязный, с глюками. Алгоритм можно переоборудовать в динамический, никакие предрасчеты не нужны.
И не ставь на него свой копирайт : )

Ну, например, так. Сначала находишь сумму всех элементов и упорядочиваешь их по возрастанию. Потом создаёшь второй массив и пробуешь туда запихнуть числа из первого массива так чтобы их сумма во втором массиве не превышала половины общей суммы. Если запихиваются, оставляешь их во втором массиве, если нет - возвращаешь в первый. Начинать надо с самых больших элементов и так пройтись по всему первому массиву в порядке убывания. После этого сумма элементов в обоих массивах будет примерно одинакова.

Пимерно так:
Сортируеш по возрастанию, потом находиш среднее орифметическое - максимально близкое к орифметическому принемаеш за середину, от середны береш один слева другой справа - в одну группу потом опять один справа другой слева в другую группу,