Need help with sorting algorithm

help /prog/,
I am really bad with all kinds of sorting algorithms
and now I need to write a really complex one:
I got 10 instances, each consisting of two integers.
Now I want to put them into two halves, 5 in each.
However the sum of the first integer in each of both halves got to be as close to the sum of the other half as possible,
while keeping the sums of the second integers as close as possible, too.
e.g.:
a: 7, 800
b: 4, 500
c: 6, 700
d: 1, 100
e: 1, 200
f: 5, 900
g: 4, 700
h: 2, 300
i: 9, 400
j: 3, 900

becomes:
i: 9, 400
f: 5, 900
b: 4, 500
h: 2, 300
d: 1, 200
---------- sum: 21, 2300
a: 7, 800
c: 6, 700
g: 4, 700
j: 3, 900
e: 1, 100
---------- sum: 21, 3200

becomes:
i: 9, 400
g: 4, 700
b: 4, 500
j: 3, 900
d: 1, 200
---------- sum: 21, 2700
a: 7, 800
c: 6, 700
f: 5, 900
h: 2, 300
e: 1, 100
---------- sum: 21, 2800

does anyone have an idea how to set up a sort, which returns these results?

Hi, fagatini.

So, you want to divide a set of integers into two partitions such that the difference between the sum of each is minimal? Forget it, it's NP hard.

I think this can't be implemented elegantly and one'd have to resort to bruteforcing.

It got to be possible. I know a website, where they do exactly that. And bruteforcing it is the last solution I'd accept.
This is simply a matter of math I think.

Turns out it's just the optimization variant of the partition problem.

>>6
ah thanks, that really helps
now I only gotta figure out how to write that in javascript
should be easy tho

>>7
Forget it, the partition problem is NP-complete.

>>8
I see, first time I ever heard of that whole NP stuff.
So, how do I use Approximation or Heuristic to get me something close to a result?

>>9
Exchange two random numbers, then put them back if the sums don't come any closer. Repeat ad nauseum.

This, by the way, is called the Monte Carlo method. Read about it on wikipedia.

^{:GJS1M 67dcbdbce4a0b67c4b48e86a6ae29205a95e4b83024a9d947213d1231800e8d9
:47 a0c3fbecbfc7b76aa114b7c8b79d3be5
:1309524849 1309528998}
>>7
<-- check my doubles

Also, it's a greedy algorithm, i.e. it might get stuck in a local minimum without discovering the true minima. But it's probably good enough for your purposes.

>>10
wikipedia named these:
Approximation
Randomization
Restriction
Parameterization
Heuristic

The Monte Carlo method would be Randomization and I thought Approximation and Heuristic sound better.

Don't overthink it, if it is always 10 numbers, bruteforcing is not a problem.

Yeah, you just have 32 possibilities to bruteforce.

thanks for the advice, I'll just go with bruteforce