Sort it with your favorite nlogn sorting algo. The bottom half is one team, the top half the other.
Or much better , partition it with median as pivot . Time complexity O(n).
