N particles can have at most N/2 collisions, so no more than N/2 “find next collision and cull the particles” are needed