Team Sorting Algorithm

I've been thinking about the issue of team sorting. It's already been mentioned in another thread (TDM Team Balancing.) that teams can get unbalanced during a game, but I have thoughts on the sorting at the beginning of a round.

Looking at the source (gameobject::getteam(int) at gs_game.cpp:234), players are assigned in order of connection based on which team has the fewest players, favouring team 0 (red), which is fine as a basic algorithm.

The aforementioned thread suggested having teams balanced by their scores in the previous game, which could be a function of what proportion of time was spent in the last game. This involves collecting and storing a bunch of data between matches, which could be fun (read: annoying) to implement.

An easier system to develop could be
- When the client joins, the server sends three ping-type packets with maybe 0.2s between them to the client
- The client responds with pongs as it receives them
- The server averages the latencies for each player
- Lots of clients are connecting at once, so the server places the clients in a FIFO queue, firing at one second intervals for two teams, which are chosen by ping, and then if one queue runs out, players from the other queue are moved across to the other queue to keep numbers even.

So, if we have A 50ms, B 80ms, C 100ms, D 150ms, E 250ms, F 120ms joining in the order A, C, D, B, E, F:

A joins and is placed in queue for team red.
C joins and is placed in queue for team blue because team red's average of 50ms is higher than team blue's 0ms.
D joins and due to having a high ping, is put into the team red queue to reduce the average ping imbalance.
B joins and is placed in queue for team blue, as the pings are currently balanced, so it falls back to filling up the spots evenly
E joins and has the higher ping, so is placed in team blue.
F joins and has a low ping, but because at this stage red has average ping 100ms vs blue's 143.3, is put in the blue queue.

Now we have:
Red: A, D
Blue: C, B, E, F

As the three second queue runs out, A and C are placed into their respective teams, as are D and B, but then there is no one for team red, so the one behind E, which is F, is pushed up to red, and we end up with A, D and F on red (average 106.7ms) and C, B and F on blue (average 100ms) for a difference of about 7ms.

With the currently used algorithm, we would have A, D and E on red (average 150) and C, B and F on blue (average 100) for a difference of 50ms.

It's not fool-proof, but I find that you get people with a wide variety of pings playing. I'm shocked in fact at how many people will play for long periods with a ping of 300-400ms. It only takes a couple of people on a ping of 50 to get on one team and things get significantly unbalanced and unfun.

Possibly I've over-analysed it a bit. I would offer to write a patch but I really don't have the time right now. I'm not saying that this is the best way to do it either. My main aim is to start some discussion on the best way of doing this.

What are everyone's thoughts?