Well, if you would be using a grid, then it could be easly achieved with arrays, but I guess you aren't using grid.
Therefore, you could do it this way:
Create (sample) 10x10 array of type/class that will hold all sprite's positions inside (if you use Tier 2, use vector for that). When spawning a sprite, check to which field will it be attached. When you know it's for example grid 2x5, check if that sprite doesn't overlap with any other sprite inside that one grid.
This will increase collision check speed, as you check for collision, but only for sprites inside that one field. (There won't be
that many sprites I suppose?)
Field's size is specified by you.
Additional:
How to check to which grid that sprite belongs?
When you have a field of, say, 100x100 pixels, and you have 10x10 fields you can do it this way:
Get sprite's X and divide it by 100, then turn the result into integer. This is field's X in array. Same goes for Y.
In the result, you'll have, for example, if your sprite's X was 234 and it's Y was 123, then corresponding field will be: [1][2] (Y, X).
I hope it's clear, but it's hard to explain such complicated thing.
Baxslash probably gave you easier way, but my way can be used across engines/APIs without need to use Box2d.
