I'll just combine two previous hints.
Use bubble sort and THEN use random.

Use bubble sort and THEN assert that the balls are the same color in (n / 2) and (n / 2 + 1)