I'm developing a 2d game that requires the sprites to be z-order sorted but am not sure how to go about doing this. Basically the sprites move around a rectangular space at angles of 45 degrees. The sprite that the user controls can move in the normal four directions and also diagonally. As they overlap each other the sprites higher up the screen need to be drawn first. Should I base the sort on the Y-axis or have a separate variable ? I also don't want to sort the sprites every frame so how should I be checking to know when to resort the list ?

I have put together a short video that shows the game running so you can see the sprite movement. I don't expect there to be more than 6 moving sprites on screen at anyone time.

http://uk.youtube.com/watch?v=tl9ls02onj0