I am working on a 2d arcade "shootem up" game and I have had no problems with speed in my department. Since I do software rendering(SDL) all CPU power which get's used is the refresh part. In any case I use 2 things.

Layers: if you can, layer objects which can hit themselves into lists(use arrays if you require superspeed)

Constant Y sorting: I do this, but not because of collision per se, but to see which get's blitted when. (I can "hide" behind objects with player). I use a typical bubblesort for this with "cancel" and "backtrack" effect.
Typical requirement is O(n + # of exchanged positions)
So if nothing changes it's a O(n) pass. I tested it and it was MUCH better than with original quicksort. But it depends on situation.

However as I sayed, unless you really do stuff ALL the time(no pause, or max. framerate) your game will take almost 0CPU without refreshing the screen and blitting(just try it for fun )