If you have a very large number of sprites, it might be time to let hardware handle it and move your sprite rendering into VBOs via pygl or the like. Realistically though, massive numbers of sprites can usually be turned on it's head as a "find the sprite under this pixel" problem instead. Maybe not so easy in python, but you might find a library already written for "particles" that handles this situation better. Collecting your sprites by wich frame they are on for example.
A good answer to this question would require a bit more knowledge about the type, speed, clumping, or even how regular the sprites might be. Do you have thousands of sprites because there are that many entities? or is it moving land-pieces? do they move in groups? Each assumption we can make about the sprites can offer a better / faster rendering solution.
As usual, what is your input data, and what do you want out.