Кстати, про сорт. Видел этот вариант задачи на собесах, где до полного счастья требуют от сортировки отказаться. Только хардкор и страдания :)
ну, тут сортировка не сильно помогает конкретно для этого решения
а так, можно и без сортировки найти самое близкое решение. очевидный вариант: находим все возможные комбинации для разбиения на два массива, берём лучший вариант)
долго, некрасиво, тупо, в лоб, но зато максимально точно)