physics - Are collision detection always O(n^2)?

Are physics engine able to decrease that complexity, for example by grouping objects who are near each other and check for collisions inside this group instead of against all objects ? (for example, far objects can be removed from a group by looking at its velocity and distance from other objects).

If not, does that make collision trivial for spheres (in 3d) or disk (in 2d) ? Should I make a double loop, or create an array of pairs instead ?

EDIT: For physics engine like bullet and box2d, is collision detection still O(N^2) ?