Algorithm of split graph $G=(V,E)$ to 2 groups that at least half of the edges are between the groups
The solution and the analysis is given in Section 6.2.1 and 6.3 of the Book: Probability and Computing
Randomized Algorithms and Probabilistic Analysis
Sometimes it is better to refer to a book rather than formulating an answer by ourselves :)