What is the most effecient way to do this? Is there a way to store all the sprites coordinates in some data-structure that keeps track of all collision?
I find comparing each sprite with all sprites is a bad idea.
I see you're also asking whether or not it is smart to test each and every sprite against each and every other sprite, because that has a BigO of n^2, which is pretty slow. Faster methods largely depend on what exactly your game is like. If you have a 2D grid-type game, you can of course simply check array locations, which is very efficient but not logical for most modern games.
Here is what I use and recommend for a top-down 2D grid-style game. I have no idea if it is the best way or not, I usually come up with my own ways of doing things.
Have a 2D array to represent all sprites that might need collision testing. Say you have a 30x30 grid to represent you entire level, each grid space being 50 pixels wide/tall. Your collision array should represent each block and the blocks surrounding it, so a 10x10 grid with each grid space being 150 pixels wide/tall. Then, every timestep, adjust every collidable sprite to the correct position within the grid. Say it is currently at 350,100 on the screen. That means it should be moved to  in the grid, because every 150 pixels it should move to different location. Then when calculating collision you only check within each sprite's collision grid space. The efficiency of doing it this way is BigO n, significantly faster than BigO n^2, although I doubt the fastest possible.
Understand what I mean?